相关参考文献
注意：仅列出部分参考文献，下载原文获取全部文献信息。Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs
Amey Bhangale et al.
2020 IEEE 61ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2020) (2020)
Fourier and Circulant Matrices are Not Rigid
Zeev Dvir et al.
THEORY OF COMPUTING (2020)
Matrix Rigidity and the Croot-Lev-Pach Lemma
Zeev Dvir et al.
THEORY OF COMPUTING (2019)
Explicit two-source extractors and resilient functions
Eshan Chattopadhyay et al.
ANNALS OF MATHEMATICS (2019)
Static Data Structure Lower Bounds Imply Rigidity
Zeev Dvir et al.
PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19) (2019)
Efficient Construction of Rigid Matrices Using an NP Oracle
Josh Alman et al.
2019 IEEE 60TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2019) (2019)
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
Kasper Green Larsen et al.
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2018)
Probabilistic Rank and Matrix Rigidity
Josh Alman et al.
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2017)
An Efficient Reduction from Two-Source to Non-malleable Extractors Achieving Near-Logarithmic Min-entropy
Avraham Ben-Aroya et al.
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2017)
Towards Optimal Two-Source Extractors and Ramsey Graphs
Gil Cohen
STOC'17: PROCEEDINGS OF THE 49TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (2017)
ARITHMETIC CIRCUITS: A CHASM AT DEPTH 3
Ankit Gupta et al.
SIAM JOURNAL ON COMPUTING (2016)
Improved bounds for reduction to depth 4 and depth 3
Sebastien Tavenas
INFORMATION AND COMPUTATION (2015)
HITTING-SETS FOR ROABP AND SUM OF SET-MULTILINEAR CIRCUITS
Manindra Agrawal et al.
SIAM JOURNAL ON COMPUTING (2015)
ON RANGE SEARCHING IN THE GROUP MODEL AND COMBINATORIAL DISCREPANCY
Kasper Green Larsen
SIAM JOURNAL ON COMPUTING (2014)
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
Anna Gal et al.
IEEE TRANSACTIONS ON INFORMATION THEORY (2013)
Arithmetic circuits: The chasm at depth four gets wider
Pascal Koiran
THEORETICAL COMPUTER SCIENCE (2012)
Logarithmic lower bounds in the cell-probe model
M Patrascu et al.
SIAM JOURNAL ON COMPUTING (2006)
Lower bounds for matrix product in bounded depth circuits with arbitrary gates
R Raz et al.
SIAM JOURNAL ON COMPUTING (2003)
A note on the use of determinant for proving lower bounds on the size of linear circuits
P Pudlák
INFORMATION PROCESSING LETTERS (2000)
Bounds for dispersers, extractors, and depth-two superconcentrators
J Radhakrishnan et al.
SIAM JOURNAL ON DISCRETE MATHEMATICS (2000)
分享论文
