The Generalized Linial-Nisan Conjecture is false
In a post a year and a half ago, I offered a prize of $200 for proving something called the Generalized Linial-Nisan Conjecture, which basically said that almost k-wise independent distributions fool AC0 circuits. (Go over to that post if you want to know what that means and why I cared about it.)
Well, I’m pleased to report that that’s a particular $200 I’ll never have to pay. I just uploaded a new preprint to ECCC, entitled A Counterexample to the Generalized Linial-Nisan Conjecture. (That’s the great thing about research: no matter what happens, you get a paper out of it.)
A couple friends commented that it was wise to name the ill-fated conjecture after other people rather than myself. (Then again, who the hell names a conjecture after themselves?)
If you don’t feel like downloading the ECCC preprint, but do feel like scrolling down, here’s the abstract (with a few links inserted):
In earlier work, we gave an oracle separating the relational versions of BQP and the polynomial hierarchy, and showed that an oracle separating the decision versions would follow from what we called the Generalized Linial-Nisan (GLN) Conjecture: that “almost k-wise independent” distributions are indistinguishable from the uniform distribution by constant-depth circuits. The original Linial-Nisan Conjecture was recently proved by Braverman; we offered a $200 prize for the generalized version. In this paper, we save ourselves $200 by showing that the GLN Conjecture is false, at least for circuits of depth 3 and higher.
As a byproduct, our counterexample also implies that Π2p⊄PNP relative to a random oracle with probability 1. It has been conjectured since the 1980s that PH is infinite relative to a random oracle, but the best previous result was NP≠coNP relative to a random oracle.
Finally, our counterexample implies that the famous results of Linial, Mansour, and Nisan, on the structure of AC0 functions, cannot be improved in several interesting respects.
To dispel any confusion, the $200 prize still stands for the original problem that the GLN Conjecture was meant to solve: namely, giving an oracle relative to which BQP is not in PH. As I say in the paper, I remain optimistic about the prospects for solving that problem by a different approach, such as an elegant one recently proposed by Bill Fefferman and Chris Umans. Also, it’s still possible that the GLN Conjecture is true for depth-two AC0 circuits (i.e., DNF formulas). If so, that would imply the existence of an oracle relative to which BQP is not in AM—already a 17-year-old open problem—and net a respectable $100.
Follow
Comment #1 July 11th, 2010 at 10:33 am
Are weaker versions of the BQP vs AM question still open? For example, do we have an oracle relative to which QMA is not in AM? What about QAM or QIP(2)?
Comment #2 July 11th, 2010 at 11:53 am
Robin: Great questions! The answer is that, alas, we don’t have oracles relative to which any of those classes are not in AM.
I did think a little about whether QMA vs. AM would be any easier than BQP vs. AM, but I couldn’t come up with a good candidate oracle problem for QMA\AM that wasn’t also a candidate for BQP\AM. The one good oracle problem in QMA that we had was Group Non-Membership, but my paper with Greg Kuperberg showed that it’s probably in QCMA also, and at any rate we have no idea how to use it for oracle separations.
Since QAM=BP.QMA, I believe that the relativized QAM vs. AM question will be essentially the same as the relativized QMA vs. AM question.
I didn’t think at all about QIP(2), that most uncharted of quantum complexity classes. AFAIK, we don’t even have a single example of a problem that’s in QIP(2) for nontrivial reasons (i.e., not because it’s in BQP, AM, etc.)!
Comment #3 July 11th, 2010 at 12:10 pm
at any rate we have no idea how to use it for oracle separations.
Or rather, as Scott pointed out when we did this work, it is rigorously useless for an oracle separation, since it is in the polynomial query version of QCMA. In other words, we proved that you can get rid of the oracle with polynomial overhead.
It’s also true that we conjectured that it’s in QCMA outright. But, caveat: Our evidence for that conjecture is based on some well-known open problems in algorithmic group theory.
Comment #4 July 11th, 2010 at 12:47 pm
Greg: The fact that GNM has polynomial QCMA query complexity doesn’t, by itself, make the problem “rigorously useless” for oracle separations—it just means that any oracle separation based on GNM would have to separate not just QMA from AM, but also QCMA.
Although, now that I think about it, the real reason GNM is “rigorously useless” for this problem is the separate fact, proved by Babai, that GNM is in AM!
Comment #5 July 11th, 2010 at 2:29 pm
Sorry, I meant rigorously useless for an oracle separation between QMA and QCMA. I lost track of the context.
Comment #6 July 11th, 2010 at 7:21 pm
Is there an easy example of two classes A and B, defined in different ways, but known to be equal, and yet for which there is an oracle separating them? This would be the case if P=NP but that equality is not known.
Comment #7 July 11th, 2010 at 7:23 pm
Oops, ignore previous, it was posted to the wrong thread and was also already answered in the other thread. Though, IP=PSPACE is quite difficult to prove, from what I understand.