With Probability One, a Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy

Abstract

We consider how much error a fixed depth Boolean circuit has to make for computing the parity function. We show that with an exponential bound of the form $exp(n^{\lambda})$ on the size of the circuits, they make asymptotically 50% error on all possible input, uniformly. As a consequence, we show that with a random oracle set $A,Pr.(PSPACE^{A} \supseteq PH^{A} = 1$.