Average-case rigidity lower bounds
From MaRDI portal
Publication:2117087
DOI10.1007/978-3-030-79416-3_11OpenAlexW3177031611MaRDI QIDQ2117087FDOQ2117087
Authors: Xuangui Huang, Emanuele Viola 
Publication date: 21 March 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-79416-3_11
Cites Work
- Title not available (Why is that?)
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Separating Nondeterministic Time Complexity Classes
- Improving exhaustive search implies superpolynomial lower bounds
- On Yao's XOR-lemma
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Short PCPs with projection queries
- A Turing machine time hierarchy
- A hierarchy for nondeterministic time complexity
- Nonuniform ACC circuit lower bounds
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- New algorithms and lower bounds for circuits with linear threshold gates
- Natural proofs versus derandomization
- Strong average-case lower bounds from non-trivial derandomization
- An average-case lower bound against \(\mathsf{ACC}^0\)
- Title not available (Why is that?)
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
- Title not available (Why is that?)
- Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
Cited In (4)
This page was built for publication: Average-case rigidity lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117087)
