You have likely heard of the new result by Ben Roco, and Li-Yang on random oracles (

see here for preprint) from either

Lance or

Scott or some other source:

Lance's headline was

*PH infinite under random oracle*
Scott's headline was

*Two papers *but when he stated the result he also stated it as a random oracle result.

The paper itself has the title

*An average case depth hierarchy theorem for Boolean circuits*
and the abstract is:

We prove an average-case depth hierarchy theorem for Boolean circuits over
the standard basis of

AND,

OR, and

NOT gates.
Our hierarchy theorem says that for every

d≥2, there is an explicit

n-variable Boolean function

f, computed by a linear-size depth-

d formula,
which is such that any depth-

(d−1) circuit that agrees with

f on

(1/2+on(1)) fraction of all inputs must have size

exp(nΩ(1/d)). This
answers an open question posed by Hastad in his Ph.D. thesis.

Our average-case depth hierarchy theorem implies that the polynomial
hierarchy is infinite relative to a random oracle with probability 1,
confirming a conjecture of Hastad, Cai, and Babai. We also use our result
to show that there is no "approximate converse" to the results of Linial,
Mansour, Nisan and Boppana on the total influence of small-depth circuits, thus
answering a question posed by O'Donnell, Kalai, and Hatami.

A key ingredient in our proof is a notion of \emph{random projections} which
generalize random restrictions.

Note that they emphasize the circuit aspect.

In Yao's paper where he showed PARITY in constant dept requires exp size the title was

*Separating the polynomial hiearchy by oracles*
Hastad's paper and book had titles about circuits, not oracles.

* *
When Scott showed that for a random oracle P^NP is properly in Sigma_2^p the title was

*Counterexample to the general Linial-Nissan Conjecture*
However the abstarct begins with a statement of the oracle result.

SO, here is the real question: What is more interesting, the circuit lower bounds or the oracle results that follow? The authors titles and abstracts might tell you what they are thinking, then again they might not. For example, I can't really claim to know that Yao cared about oracles more than circuits.

Roughly speaking the Circuit results are interesting since they are actual lower bounds, often on reasonable models for natural problems (both of these statements can be counter-argued), oracle results are interesting since they give us a sense that certain proof teachniques are not going to work. Random oracle results are interesting since for classes like these (that is not well defined) things true for random oracles tend to be things we think are true.

But I want to hear from you, the reader: For example which of PARITY NOT IN AC_0 and THERE IS AN ORACLE SEP PH FROM PSPACE do you find more interesting? Is easier to motivate to other theorists? To non-theorists (for non-theorists I think PARITY).