Yet Another Proof that \(\mathsf{BPP} \subseteq \mathsf{PH}\)
Abstract
We present a new, simplified proof that the complexity class \(\mathsf {BPP}\) is contained in the Polynomial Hierarchy \(\mathsf {(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).
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Algorithms and Data Compression
Cryptography and Data Security
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 551–556
- Publication date
- 1 January 2026
- Language
- EN