mathemagicio.us

Virtually everyone with a CS blog (see Scott Aaronson, Luca Trevisan, and the Complexity Blog) has for the past several weeks been going on about Mark Braverman’s recent proof of the Linial-Nisan conjecture. I don’t have too much to add to the discussion, being a neophyte to much of this stuff, but I did attend a talk Braverman gave at the University of Calgary today, in which he outlined his proof (which is remarkably short, for a proof of a conjecture that took nearly 20 years to solve.) Braverman illustrated his arguments with pictures, which really helped me get a handle on his techniques.

The content of the theorem relates to what strength of pseudo-randomness is “good enough” to fool circuits of a significantly limited size and depth into thinking the pseudo-randomness is truly random. As an analogy, the D in HD video is becoming ever and ever more H (currently we’re up to a resolution of 7680×4320) but our brains have a finite capacity and our eyes aren’t perfect lenses. Increase the resolution high enough, and eventually we won’t be able to tell the difference between the HD video signal and a “true” view of the world. Similarly, we’d like to know whether certain limited models of computation can tell apart real randomness from approximate randomness.

The Linial-Nisan conjecture restricts us to logical circuits used to compute answers to decision problems/boolean functions F¹ made up of AND, OR and NOT gates², where the number of gates is allowed to be polynomial in size³  but the depth of the circuit must remain constant across all instances.

This class of circuits is called AC⁰, and these conditions are more restrictive than they first seem. You might point out that any boolean function whatsoever can be computed by a depth-2 circuit (for example, in disjunctive normal form.) And that’s true, but the number of gates then required might be superpolynomial in size. For example, even doing something as relatively simple as computing the parity of n bits cannot be done in AC⁰—you either need to increase the depth of the circuit as the problem grows in size, or have access to more complicated gates, or use more than a polynomial number of gates.

The question, then, is what kind of probability distributions over {0,1}ⁿ look identical to the uniform distribution to AC⁰ circuits. In particular, the Linial-Nisan conjecture asks about distributions that are uniform when you restrict them to any k < n bits, but are no longer uniform as a whole. For example, consider  chosen uniformly, and . The last variable is determined entirely by the others so the n bits as a whole aren’t uniformly random, but if you pick any k = n-1 bits at a time you do get a uniform distribution. Do such distributions look uniform to AC⁰ circuits? And if so, how small can k be? (Imagine a distribution half of whose bits are determined by the others. Can such a fundamentally non-random distribution be detected by an AC⁰ circuit?)

Mark Braverman proved that k can be very low indeed. It need only be polylogarithmic (for example, of order for depth-2 circuits, in m being the number of gates.) In general, the exponent is quadratic in the depth to which we restrict ourselves. Asymptotically, this is tiny! And many suspect this bound is still too high, as suffices for depth-2 circuits, leading to the suspicion that the tight bound is .

How does Braverman prove this result? He constructs low-degree polynomials that sufficiently approximate and “sandwich” the function F in question (think of the squeeze theorem from your Calculus 1 days), which was previously known to be sufficient to prove the result.

The first kind of approximating polynomials are due to Linial, Manser and Nisan way back in 1993. These LMN polynomials are created by taking the canonical, polynomial expansion of the function (for example, by interpolation) and simply chopping off the high-order terms. Such polynomials approximate F very well on average, but may not be equal to F at many, if any points. In other words, there is a small distance between them.

LMN approximation (red) to a boolean function F (black)

The second kind of approximation is due to Razborov and Smolensky. This time, the approximating polynomial agrees with the function F on most inputs, but it may behave wildly wherever it doesn’t.

Razborov-Smolensky approximation (blue) of the same function

(In fact, the jumpiness in the blue graph can be far more wild than the picture suggests, making it an awful approximation at these points.) At any rate, neither of these approximations behave quite the way we want them to. What we’d like is a low-degree approximation of F that agrees with it on most inputs (as in the blue approximation) and doesn’t stray too far away when it doesn’t (as in the red approximation.)

What Braverman discovered is that although the blue approximation can be very, very wrong at some points, this error can be checked in AC⁰! In particular, there’s a AC⁰ function ε that takes on the value 1 whenever the blue approximation disagrees with F (and possibly at some other points that give false positives, but not too many.) This function ε tells us when we need to correct the blue approximation. Then, Braverman applies the red, wavy approximation to ε and takes its negation, giving us a low-degree polynomial which (nearly) vanishes whenever the blue approximation is inaccurate.

Approximation of 1-ε (orange)

Then he just multiplies the blue and orange functions together to create a new approximation! Doing this kills the blue guy whenever he misbehaves, resulting in a polynomial that approximates F in the nice ways we wanted, and which is still of low-enough degree to be usable.

That’s pretty much all there is to it! All that’s left to do is to fill in the gaps with some algebraic magic, and the claim is proved. Not bad at all.

¹ For example, is x prime? Or, does the input graph have a vertex of degree 5?
² We allow the AND and OR gates to take any number of inputs, rather than only two.
³ For example, the circuit that computes the answer for inputs of size n could have n¹³ gates.

Complexity, CS