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 .

Continue reading →