Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > THE POLYNOMIAL-TIME HIERARCHY:
Reports tagged with The Polynomial-Time Hierarchy:
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 ... more >>>




ISSN 1433-8092 | Imprint