Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SIMPLIFIED PROOF:
Reports tagged with Simplified Proof:
TR26-004 | 16th January 2026
Ilya Volkovich

Yet Another Proof that $BPP \subseteq PH$

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, ... more >>>




ISSN 1433-8092 | Imprint