Wednesday, April 22, 2015

The New Oracle Result! The new circuit result! which do you care about?

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 d2, there is an explicit n-variable Boolean function f, computed by a linear-size depth-d formula, which is such that any depth-(d1) 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).


  1. In part because I am of a certain age, I would have been more likely to say "wow!" upon first seeing the paper had it been titled "The Polynomial-Time Hierarchy is Infinite Relative to a Random Oracle." The problem was open for so long I had forgotten it was open. Of course... I read Lance's post "PH Infinite Under a Random Oracle" first, so the "wow!" opportunity was not missed.

    That said, the circuit results are surely more interesting. For one thing, they are stronger (they imply the oracle results as well as other things; and they are not equivalent). Second, they are another (very very small) step in the quest for stronger circuit lower bounds. For the same reason I agree that Parity not in AC_0 (etc.) is more interesting than \exists A (ParityP^A not in PH^A). Come to think of it, it's also easier to write down!

  2. I second Fred. Lower bounds for circuits imply other results. But I haven't seen things happening other way around. (Ryan has shown that a reverse traffic could also exist, but this is just a rare and nice exception so far.) Also, to write what an "oracle separation" means will require 2-3 pages (at least). To write what a lower bound for circuits means - just 3-4 sentences. The introduction being: few AND-OR-NOT on 0-1 bits - and what can we get?

    But it is definitely nice that circuits are related to more "exotic" things like oracles. Anyone can choose what to love: root or tree. Both are important. Without the tree, root (hard root - progress is SO slow, adversary is So powerful) couldn't survive ... But died the root, the tree would definitely die.

  3. As you may remember, Bill, I was doing recursion theory as a grad student and shifted over to work with Mike on circuit complexity. The key moment in that evolution was a talk by Cook on his "taxonomy" paper -- "Here are these circuit classes, they classify the difficulty of computing things in parallel, here are some interesting containments, can we get any separations?" I think that I was among the first people to use the name "AC^0" for constant depth, polynomial size, unbounded fan-in, which brings Furst-Saxe-Sipser-Ajtai into the context of the NC hierarchy.

    So I definitely think the circuit results are more interesting for themselves than for their applications as oracle results. Even though the program of extending these results upward to larger circuit classes (like P) hasn't panned out and may never pan out, a concrete lower bound ("you can't solve this problem with these resources") adds more to what we know about general computation.