When I decided to move, I was very impressed by Stanford’s computer science department’s plan to hire a new complexity theorist every other year, so that the department would be entirely composed of complexity theorists by 2100.
So far we are on track, and I am very excited to welcome our new colleague Ryan Williams.
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.
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 .