Random oracles separate PSPACE from the polynomial-time hierarchy
By confirming a conjecture of \textit{M. Furst}, \textit{J. B. Saxe} and \textit{M. Sipser} [Math. Syst. Theory 17, 13-27 (1984; Zbl 0534.94008)] on the size of constant-depth parity circuits, \textit{A. C. Yao} [Separating the polynomial time hierarchy by oracles, Proc. 26th FOCS, 1-10 (1985)] has completed the proof that PSPACE is separated from the polynomial-time hierarchy by some oracles. \textit{J. Cai} [With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy, Proc. 18th STOC, 21-29 (1986); cf. Lect. Notes Comput. Sci. 223, 104 (1986) and J. Comput. Syst. Sci. 38, No.1, 68-85 (1989)] modified Yao's complex argument to prove that this separation occurs relative to almost every oracle. We prove that this result actually follows immediately from Yao's theorem, using a simple construction of \textit{M. Ajtai} and \textit{M. Ben- Or} [A theorem on probabilistic constant depth computation, Proc. 16th ACM STOC, 471-474 (1984)] to eliminate randomization in bounded-depth Boolean circuits.
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- On random oracle separations
- Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
- Circuit size relative to pseudorandom oracles
- An oracle separating \(\oplus P\) from \(PP^{PH}\)
- Cryptography with constant input locality
- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
- The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
- Circuit depth relative to a random oracle
- Circuit size relative to pseudorandom oracles
- The generic oracle hypothesis is false
- The power of adaptiveness and additional queries in random-self- reductions
- When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
- Enumerative counting is hard
- Hardness of learning problems over Burnside groups of exponent 3
- Finite groups and complexity theory: from Leningrad to Saint Petersburg via Las Vegas
- Parity, circuits, and the polynomial-time hierarchy
- scientific article; zbMATH DE number 4125012 (Why is no real title available?)
- Interleaved Group Products
- On the correlation of symmetric functions
- On closure properties of bounded two-sided error complexity classes
- On the correlation of symmetric functions
- Strong self-reducibility precludes strong immunity
- An information-theoretic treatment of random-self-reducibility (extended abstract)
- Polynomial-time random oracles and separating complexity classes
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions
- Worst-Case to Average-Case Reductions for Subclasses of P
- Sampling lower bounds: Boolean average-case and permutations
- On the power of parity polynomial time
- Improved pseudorandom generators from pseudorandom multi-switching lemmas
- Borel complexity and Ramsey largeness of sets of oracles separating complexity classes
- A technique for hardness amplification against AC^0
- Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
- An oracle separating \(\oplus P\) from \(PP^{PH}\)
This page was built for publication: Random oracles separate PSPACE from the polynomial-time hierarchy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1108794)
