ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > INTERACTIVE PROOF SYSTEMS (AM AND MA):
Reports tagged with Interactive Proof Systems (AM and MA):
TR97-045 | 29th September 1997
Oded Goldreich, David Zuckerman

Another proof that BPP subseteq PH (and more).

Comments: 1
We provide another proof of the Sipser--Lautemann Theorem by which $BPP\subseteq MA$ ($\subseteq 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 ... more >>>



ISSN 1433-8092 | Imprint