Average-case rigidity lower bounds
From MaRDI portal
Publication:2117087
Cites work
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 7650350 (Why is no real title available?)
- A Turing machine time hierarchy
- A hierarchy for nondeterministic time complexity
- An average-case lower bound against \(\mathsf{ACC}^0\)
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- Improving exhaustive search implies superpolynomial lower bounds
- Inverse-exponential correlation bounds and extremely rigid matrices from a new derandomized XOR lemma
- Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms.
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Nonuniform ACC circuit lower bounds
- On Yao's XOR-lemma
- Separating Nondeterministic Time Complexity Classes
- Short PCPs with projection queries
- Strong average-case lower bounds from non-trivial derandomization
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
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)
