The Polynomial Hierarchy, Random Oracles, and Boolean Circuits.
B. Rossman and R. Servedio and L.-Y. Tan.
SIGACT News, Complexity Theory Column 89, 46(4), December 2015, pp. 50--68.


Abstract:

We give an overview of a recent result [RST15] showing that the polynomial hierarchy is infinite relative to a random oracle. Since the early 1980s it has been known that this result would follow from a certain "average-case depth hierarchy theorem" for Boolean circuits. In this article we present some background and history of related relativized separations; sketch the argument showing how the polynomial hierarchy result follows from the circuit lower bound; and explain the techniques underlying the new circuit lower bound.

pdf


Back to main papers page