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
Recommendations
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
- Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
- On circuit lower bounds from derandomization
- Circuit lower bounds for Merlin-Arthur classes
- Circuit lower bounds for Merlin-Arthur classes
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Lower bounds for the size of nondeterministic circuits
- scientific article; zbMATH DE number 2080255
- Derandomizing Arthur-Merlin games under uniform assumptions
- Tighter connections between derandomization and circuit lower bounds
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
- 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
- Title not available (Why is that?)
- 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 (11)
- 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
- Holographic Proofs and Derandomization
- Pseudorandomness for approximate counting and sampling
- Natural proofs versus derandomization
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Title not available (Why is that?)
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
- 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)
