Complexity Theory Column 89: The Polynomial Hierarchy, Random Oracles,
Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan · 2015
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.