Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
DOI10.1137/18M1195887zbMath1494.68096OpenAlexW3009964738WikidataQ124882178 ScholiaQ124882178MaRDI QIDQ5130843
Cody D. Murray, R. Ryan Williams
Publication date: 29 October 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1195887
lower boundssatisfiabilitycircuit complexitynondeterminismpseudorandomnessACCMerlin-Arthur protocols
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On uniformity and circuit lower bounds
- A Turing machine time hierarchy
- Turing machines that take advice
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- On ACC
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Robust simulations and significant separations
- Pseudorandomness and average-case complexity via uniform reductions
- Efficient learning algorithms yield circuit lower bounds
- Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
- Natural Proofs versus Derandomization
- Improving Exhaustive Search Implies Superpolynomial Lower Bounds
- Some New Consequences of the Hypothesis That P Has Fixed Polynomial-Size Circuits
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Nonuniform ACC Circuit Lower Bounds
- Circuit-size lower bounds and non-reducibility to sparse sets
- Local Reductions
- Circuit Lower Bounds for Merlin–Arthur Classes
- Separating Nondeterministic Time Complexity Classes
- New Collapse Consequences of NP Having Small Circuits
- Algebraic methods for interactive proof systems
- Quantum Computability
- New algorithms and lower bounds for circuits with linear threshold gates
- Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
- Short PCPs with Projection Queries
- Computational Complexity
- New non-uniform lower bounds for uniform classes
- Pseudo-random generators for all hardnesses
- Pseudorandom generators without the XOR lemma
