Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
From MaRDI portal
Publication:645124
Recommendations
Cites work
- scientific article; zbMATH DE number 1335875 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- scientific article; zbMATH DE number 1405686 (Why is no real title available?)
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Circuit lower bounds for Merlin-Arthur classes
- Circuit-size lower bounds and non-reducibility to sparse sets
- Computational Complexity
- Computational Complexity
- Derandomizing Arthur-Merlin games using hitting sets
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
- Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Hardness vs randomness
- Hardness-randomness tradeoffs for bounded depth arithmetic circuits
- How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Oracles and queries that are sufficient for exact learning
- Proving SAT does not have small circuits with an application to the two queries problem
- Pseudo-random generators for all hardnesses
- Pseudorandom Bits for Constant‐Depth Circuits with Few Arbitrary Symmetric Gates
- Pseudorandom Generators and Typically-Correct Derandomization
- Pseudorandom bits for constant depth circuits
- Pseudorandomness for approximate counting and sampling
- Simple extractors for all min-entropies and a new pseudorandom generator
- The Knowledge Complexity of Interactive Proof Systems
- The complexity of promise problems with applications to public-key cryptography
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- \(\text{S}_{2}^{\text{P}} \subseteq \text{ZPP}^{\text{NP}}\)
Cited in
(16)- Arthur and Merlin as oracles
- scientific article; zbMATH DE number 2080255 (Why is no real title available?)
- NONDETERMINISTIC CIRCUIT MINIMIZATION PROBLEM AND DERANDOMIZING ARTHUR-MERLIN GAMES
- Circuit lower bounds for Merlin-Arthur classes
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games
- Circuit lower bounds for Merlin-Arthur classes
- Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses
- Derandomizing Arthur-Merlin games under uniform assumptions
- Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
- Circuit lower bounds from learning-theoretic approaches
- In a world of \(\mathrm{P}=\mathrm{BPP}\)
- Pseudorandomness for approximate counting and sampling
- Arthur and Merlin as Oracles
- Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
- The complexity of estimating min-entropy
- Derandomizing Arthur-Merlin games using hitting sets
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)
