REPORTS > DETAIL:
Paper:
TR97-045 | 29th September 1997 00:00
Another proof that BPP subseteq PH (and more).
TR97-045 Authors: Oded Goldreich, David Zuckerman
Publication: 1st October 1997 14:53
Downloads: 160
Keywords:
Abstract:
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 regarding $MA$: $MA\subseteq 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$.