Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
type: Item
instance of: scholarly article
title: Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
zbMATH Open document ID: 1343.68085
DOI: 10.1007/978-3-642-22670-0_6
author: Oded Goldreich
author: David Zuckerman
published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation
publication date: 2011-08-19T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5940574
zbMATH Keywords: BPP
zbMATH Keywords: polynomial-time hierarchy
zbMATH Keywords: interactive proof systems (AM and MA)
zbMATH Keywords: randomness-efficient error reduction (amplification)
MaRDI profile type: MaRDI publication profile
full work available at URL: 978-3-642-22670-0 6
OpenAlex ID: W2177219880
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: Does co-NP have short interactive proofs ?
cites work: More on BPP and the polynomial-time hierarchy
cites work: Computational Complexity
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Q4526985
cites work: BPP and the polynomial hierarchy
cites work: Derandomizing Arthur-Merlin games using hitting sets
cites work: Q3792245
cites work: A decisive characterization of BPP
cites work: Simulating BPP using a general weak random source
Recommended article: Q4390865
Recommended article: Another algebraic proof of Bondy's theorem on induced subsets
Recommended article: A constructive proof of the Bishop-Phelps-Bollobás theorem for the space \(C(K)\)
Recommended article: A recursion-theoretic characterization of instances of $ΒΣ_n$ provable in $П_{n+1}(N)$
Recommended article: An Elementary Proof of a Result on Λ(p) Sets
Recommended article: Q4271178
Recommended article: P-domination and Borel sets
Recommended article: ALTERNATIVE PROOFS OF BAER AND p.p. CONDITIONS
Recommended article: On the finite axiomatizability of
description: scientific article; zbMATH DE number 5940574