Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
DOI10.1007/S00037-014-0095-YzbMATH Open1371.68094OpenAlexW2175404758MaRDI QIDQ2012178FDOQ2012178
Bariş Aydinlioǧlu, Dieter Van Melkebeek
Publication date: 28 July 2017
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-014-0095-y
Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- 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 and approximate counting implies exponential-size lower bounds
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Some consequences of non-uniform conditions on uniform classes
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Competing provers yield improved Karp-Lipton collapse results
- Probabilistic complexity classes and lowness
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Circuit-size lower bounds and non-reducibility to sparse sets
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Turing machines that take advice
- On circuit lower bounds from derandomization
- In a World of P=BPP
- Pseudorandom generators, typically-correct derandomization, and circuit lower bounds
- Arthur and Merlin as oracles
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Two Comments on Targeted Canonical Derandomizers
Cited In (7)
- 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
- Natural proofs versus derandomization
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Title not available (Why is that?)
Recommendations
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Title not available (Why is that?) 👍 👎
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds 👍 👎
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes 👍 👎
- On circuit lower bounds from derandomization 👍 👎
- Derandomizing Arthur-Merlin games under uniform assumptions 👍 👎
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES 👍 👎
- Lower Bounds for the Size of Nondeterministic Circuits 👍 👎
- Circuit Lower Bounds for Merlin–Arthur Classes 👍 👎
This page was built for publication: Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2012178)
