Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR26-004 | 16th January 2026 00:03

Yet Another Proof that $BPP \subseteq PH$

RSS-Feed




TR26-004
Authors: Ilya Volkovich
Publication: 16th January 2026 00:12
Downloads: 136
Keywords: 


Abstract:

We present a new, simplified proof that the complexity class BPP is contained in the Polynomial Hierarchy (PH), using $k$-wise independent hashing as the main tool. We further extend this approach to recover several other previously known inclusions between complexity classes. Our techniques are inspired by the work of Bellare, Goldreich, and Petrank (Information and Computation, 2000).



ISSN 1433-8092 | Imprint