Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
DOI10.1007/S00037-011-0010-8zbMATH Open1230.68076OpenAlexW2168155538MaRDI QIDQ645124FDOQ645124
Authors: Bariş Aydinlioǧlu, Dan Gutfreund, John M. Hitchcock, Akinori Kawachi 
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
Recommendations
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Computational Complexity
- Hardness vs randomness
- Pseudorandomness for approximate counting and sampling
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Derandomizing Arthur-Merlin games using hitting sets
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- Computational Complexity
- Pseudorandom bits for constant depth circuits
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Oracles and queries that are sufficient for exact learning
- The complexity of promise problems with applications to public-key cryptography
- The Knowledge Complexity of Interactive Proof Systems
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Simple extractors for all min-entropies and a new pseudorandom generator
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- Title not available (Why is that?)
- Derandomizing polynomial identity tests means proving circuit lower bounds
- On Worst‐Case to Average‐Case Reductions for NP Problems
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Circuit-size lower bounds and non-reducibility to sparse sets
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- Pseudorandom Generators and Typically-Correct Derandomization
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Pseudo-random generators for all hardnesses
- Title not available (Why is that?)
- Title not available (Why is that?)
- Proving SAT does not have small circuits with an application to the two queries problem
- Circuit lower bounds for Merlin-Arthur classes
- Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
Cited In (15)
- The complexity of estimating min-entropy
- Derandomizing Arthur-Merlin games under uniform assumptions
- Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
- Derandomizing Arthur-Merlin games using hitting sets
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- In a world of \(\mathrm{P}=\mathrm{BPP}\)
- Arthur and Merlin as Oracles
- Pseudorandomness for approximate counting and sampling
- Circuit lower bounds from learning-theoretic approaches
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Arthur and Merlin as oracles
- Title not available (Why is that?)
- Circuit lower bounds for Merlin-Arthur classes
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
- Circuit lower bounds for Merlin-Arthur classes
This page was built for publication: Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q645124)
