Circuit Lower Bounds by Properties and by Brute Force

There are two families of approaches to proving circuit lower bounds: exploiting properties of functions computed by small circuits, and building hard functions by “brute force.” The first approach leads to “natural proofs” in the sense of Razborov and Rudich, which is a problem because natural proofs are unlikely to give lower bounds for circuit classes such as (constant-depth circuits with threshold gates), and maybe even (constant-depth circuits with AND, OR, NOT, and MOD gates). The second approach creates proofs that “algebraize,” in the sense of Aaronson and Wigderson, and algebaizing proofs construct hard functions of very high uniform complexity; it is not even possible to use an algebraizing proof to show that the huge complexity class contains problems of super-polynomial circuit complexity.

The circuit lower bound of Williams avoids both barriers, by exploiting (among other things) a property of circuits (the existence of slightly faster-than-brute-force satisfiability algorithms) that is not a “natural” property, neither is an “algebraizing” property.

This post, written by a non-expert for non-experts (but experts are welcome to read it and to point out any mistakes), describes some of the context.

A Circuit Lower Bound Breakthrough

One of the great embarrassments of research in circuit lower bounds has been the inability to prove any lower bounds for ACC0 circuits, that is bounded-depth circuits with unbounded-fan-in AND, OR, NOT, and general Modular gates. (A “mod m” gate takes boolean inputs and its boolean outpus is 0 if and only if the number of ones among the inputs is a multiple of . A “mod 2” gate is a XOR gate.)

There are two known methods to prove lower bounds for AC0 circuits (like the above, but without the modular gates). One is to argue that the function computed by a polynomial size AC0 circuit is likely to become a constant when one fixes several variables to random values; this implies that the XOR function is not in AC0 because it remains undetermined even if all but one variables are fixed. This method seems hopeless when applied to ACC0 circuits, and in fact I think that the class ACC0 was considered as a way to “turn off” the random restriction method and to consider what other approaches there are to constant-depth circuits. The other method is to approximate an AC0 circuit via a low-degree polynomial, and to show that certain functions cannot be approximated this way and hence are not in AC0. This method also works with ACC0 circuits provided that all modular gates use the same prime modulus, but it seems to break down completely if one works with a composite modulus.

In particular, the following question was open: are all problems in solvable by depth-3 circuits with unbounded fan-in AND, OR, NOT and MOD 6 gates?.

(The class contains by definition all the problems solvable in exponential time with oracle access to NP — exponentially long oracle queries are allowed.)

Finally, the embarrassment is over: in a remarkable paper, the first to put forward a new viable lower bound technique for bounded-depth circuits in two decades, Ryan Williams has proved that there are problems in NEXP (non-deterministic exponential time) that are not in ACC0, and that for every fixed depth there are problems in not solvable by ACC0 circuits of depth d and size smaller than , for some .

Replacing madness by mere disappointment

Tim Gowers is going to write about his idea for circuit lower bounds in the form of a seven-part dialog between three characters.

The first installment is out, and it already features a gentle and beautiful introduction to the models of boolean circuits and boolean formulas, and to the natural proof impossibility result. He also brings up the very interesting meta-question (which sounds rather new to me) of whether a “random easy function is pseudorandom.”

(The title of the post is how a character in the dialog refers to impossibility results such as natural proofs.)

Make your voice heard

You may remember the polymath1 project, in which Tim Gowers envisioned, and realized, a “massively collaborative” approach to solving an open question in mathematics. The project succeeded, and in fact exceeded its goal. Various subsequent polymath projects are under way, suggested by Gil Kalai and Terry Tao. Notably, Terry Tao has launched a project to find an efficient deterministic algorithm to construct large primes.

Meanwhile, Gowers has been thinking about his next polymath proposal, and he has recently written about the possible projects that he has in mind. One of the projects involves a new approach to proving circuit lower bounds. No detail of this approach is given; nor it will, unless it becomes a polymath project. Gowers would like people to comment on his post indicating which projects they are most interested in.