Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
From MaRDI portal
Publication:645124
DOI10.1007/s00037-011-0010-8zbMath1230.68076OpenAlexW2168155538MaRDI QIDQ645124
Akinori Kawachi, Dan Gutfreund, Bariş Aydinlioǧlu, John M. Hitchcock
Publication date: 8 November 2011
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-011-0010-8
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (5)
Circuit lower bounds from learning-theoretic approaches ⋮ Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games ⋮ In a World of P=BPP ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace ⋮ The complexity of estimating min-entropy
Cites Work
- Pseudorandom bits for constant depth circuits
- Derandomizing Arthur-Merlin games using hitting sets
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Oracles and queries that are sufficient for exact learning
- Pseudorandomness for approximate counting and sampling
- Proving SAT does not have small circuits with an application to the two queries problem
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Circuit-size lower bounds and non-reducibility to sparse sets
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- Simple extractors for all min-entropies and a new pseudorandom generator
- Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits
- Pseudorandom Generators and Typically-Correct Derandomization
- The complexity of promise problems with applications to public-key cryptography
- The Knowledge Complexity of Interactive Proof Systems
- Computational Complexity
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Computational Complexity
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Pseudo-random generators for all hardnesses
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
