Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)

DOI10.1007/978-3-642-22670-0_6zbMath1343.68085OpenAlexW2177219880MaRDI QIDQ3088174

Oded Goldreich, David Zuckerman

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_6

zbMATH Keywords

polynomial-time hierarchyBPPinteractive proof systems (AM and MA)randomness-efficient error reduction (amplification)

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The landscape of communication complexity classes ⋮ Average-case intractability vs. worst-case intractability ⋮ Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete ⋮ The power of natural properties as oracles ⋮ On zero error algorithms having oracle access to one query ⋮ Simplified Derandomization of BPP Using a Hitting Set Generator ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Derandomizing Arthur-Merlin games using hitting sets
• BPP and the polynomial hierarchy
• Does co-NP have short interactive proofs ?
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• More on BPP and the polynomial-time hierarchy
• Simulating BPP using a general weak random source
• The Knowledge Complexity of Interactive Proof Systems
• A decisive characterization of BPP
• Computational Complexity