Computer Science – Computational Complexity
Scientific paper
2011-10-27
Computer Science
Computational Complexity
17 pages
Scientific paper
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 Pi2P is not contained in P^NP 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 highest levels of PH previously proved separate were NP and coNP. 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.
No associations
LandOfFree
A Counterexample to the Generalized Linial-Nisan Conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Counterexample to the Generalized Linial-Nisan Conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Counterexample to the Generalized Linial-Nisan Conjecture will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-376354