I just saw in “Shtetl Optimized” that the Linial-Nisan conjecture regarding circuits have been proved by Mark Braverman. Scott’s post describes the conjecture as well as related open problems in computational complexity. (Scott offers $100 for a proof that Fourier Checking is not in AM, $200 for a proof that it’s not in PH.) After many years of no news the case of depth two circuits was proved by Louay Bazzi about a year ago and a simpler proof was found by Razborov. Here is a post on the depth two case from “In theory“.
L. Bazzi M. Braverman
All three posts describe the results in some details, Luca discusses connection with random 3SAT problems and Scott mentions some natural connections with quantum computation. Scott also gives a link to his related FOCS tutorial on the “polynomial method”.
Here is the description of Braverman’s result taken from “computational complexity”.
“Braverman shows that no poly-logarithmically independent distribution can be distinguished from a truly random distribution by a polynomial-size constant-depth circuit.
A r-independent distribution over binary strings of length n means that for every set of r bits are uniformly distributed over the 2r possible values for those bits. We can create r-independent distributions using O(r log n) truly random bits.
Braverman shows that no depth-d size-m circuit of AND, OR and NOT gates can distinguish between a truly uniform distribution and any r-independent distribution with r = (log m)O(d2). ”
Here is a problem (perhaps silly) that comes to mind: Is the conclusion of the Linial-Nisan conjecture (=Braverman’s result) holds for Monotone circuits, namely to circuits with (monotone) threshold gates? (I may ask around.) (As Luca pointed out, we can certainly cannot hope for the full statement of the theorem; I am not sure about a weak version.)