Another proof that BPP subseteq PH (and more).
Oded Goldreich, David Zuckerman · 1997
We provide another proof of the Sipser--Lautemann Theorem by which BPP ` MA (` PH). The current proof is based on strong results regarding the amplification of BPP , due to Zuckerman. Given these results, the current proof is even simpler than previous ones. Furthermore, extending the proof leads to two results regarding MA: MA ` ZPP NP (which seems to be new), and that two-sided error MA equals MA. Finally, we survey the known facts regarding the fragment of the polynomial-time hierarchy which contains MA. Keywords: BPP, The Polynomial-Time Hierarchy, Interactive Proof Systems (AM and MA), Randomness--Efficient Error Reduction (Amplification). Work done while visiting LCS, MIT. y Supported in part by NSF NYI Grant No. CCR-9457799, a David and Lucile Packard Fellowship for Science and Engineering, and an Alfred P. Sloan Research Fellowship. 1 Introduction Non-trivial results, showing containment of fundamental complexity classes in one another, are quite rare. One of the firs...