## Wednesday, August 14, 2024

### Favorite Theorems: Random Oracles

This months favorite theorem is a circuit result that implies the polynomial-time hierarchy is infinite relative to a random oracle, answering an open question that goes back to the 80's.

Johan Håstad, Benjamin Rossman, Rocco A. Servedio and Li-Yang Tan

The authors show how to separate depth d from depth d+1 circuits for random inputs. As a corollary, the polynomial hierarchy is infinite with a random oracle, which means that if we choose an oracle R at random, with probability one, the k+1-st level of the polynomial-time hierarchy relative to R is different than the k-th level relative to R.

Why should we care about random oracles? By the Kolmogorov zero-one law, every complexity statement holds with probability zero or probability one with a random oracle, so for every statement either it or its negation holds with probability one. And since the countable intersection of measure-one sets is measure one, every complexity statement true relative to a random oracle are all simultaneously true relative to a random oracle, a kind of consistent world. With a random oracle, we have full derandomization, like BPP = P, AM = NP and PH in $$\oplus\mathrm{P}$$. We have separations like P ≠ UP ≠ NP. We have results like NP doesn't have measure zero and SAT solutions can be found with non-adaptive queries to an NP oracle. And now we have that the PH is infinite simultaneously with all these other results.

More details on this paper from a post I wrote back in 2015.

1. (Bill- Gee, we can separate PH with a random oracle but we still can't adjust the setting so that I can post without being moderated. And this is not a Luddite thing- Non-Luddite Lance could not figure it out either.)

Was this a circuit result or an oracle result? Actually it was, as is typical, a circuit result that implied an oracle result. But which do we care about? If some theorem in hard math implied P NE NP the then would the title be

The p-adic cohomology of finite genus curves is prime
or
P NE NP. Really!

I did a post about oracle result vs circuit result here:

https://blog.computationalcomplexity.org/2015/04/the-new-oracle-result-new-circuit.html

Also relevant:

https://www.nbc.com/saturday-night-live/video/shimmer-floor-wax/2721424

1. It wouldn't have made my favorite list without the oracle result.