Average-case rigidity lower bounds
From MaRDI portal
Publication:2117087
DOI10.1007/978-3-030-79416-3_11MaRDI QIDQ2117087
Publication date: 21 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-79416-3_11
68Qxx: Theory of computing
Related Items
Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization, Efficient Construction of Rigid Matrices Using an NP Oracle
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- A hierarchy for nondeterministic time complexity
- An average-case lower bound against \(\mathsf{ACC}^0\)
- Natural Proofs versus Derandomization
- Improving exhaustive search implies superpolynomial lower bounds
- On Yao’s XOR-Lemma
- Nonuniform ACC Circuit Lower Bounds
- Separating Nondeterministic Time Complexity Classes
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- New algorithms and lower bounds for circuits with linear threshold gates
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Strong average-case lower bounds from non-trivial derandomization
- Short PCPs with Projection Queries
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
- Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
