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
(7)- Average-case lower bounds for the plurality problem
- Efficient Construction of Rigid Matrices Using an NP Oracle
- Majority vs. approximate linear sum and average-case complexity below NC^1
- A technique for hardness amplification against AC^0
- Rigid matrices from rectangular PCPs
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- Efficient construction of rigid matrices using an NP oracle
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)
