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 n boolean inputs and its boolean outpus is 0 if and only if the number of ones among the inputs is a multiple of m. 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 EXP^{NP} solvable by depth-3 circuits with unbounded fan-in AND, OR, NOT and MOD 6 gates?.

(The class EXP^{NP} 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 d there are problems in EXP^{NP} not solvable by ACC0 circuits of depth d and size smaller than 2^{n^\delta}, for some \delta = \delta(d)>0.

The new technique was developed in a previous paper by Ryan, and it is based on satisfiability algorithms.

For intuition, suppose for a moment that P=NP. Then, by binary search, there is a polynomial time algorithm that given the truth-table of a boolean function f: \{0,1\}^n \rightarrow \{0,1\} determines in polynomial time (that is, in time 2^{O(n)}) the size of the smallest circuit that computes f. Now, the search problem, given n, find the truth table of a function of circuit complexity at least 2^{n/2}, is an NEXP search problem and so it can be solved in EXP assuming P=NP. So if P=NP we have a proof that there are problems in EXP that require circuits of exponential size.

In a paper from earlier this year Ryan showed that circuit lower bounds can be derived even by slightly sub-exponential simulations of non-determinism. In particular, if there is an algorithm for circuit-SAT running in time, for example, 2^{n - \log^2 n}, then there are problems in NEXP that are not solvable by polynomial size circuits. Ryan shows that the existence of polynomial size circuits for NEXP, together with a non-trivially fast algorithm for circuit satisfiability would lead to sub-exponential non-deterministic algorithms for NEXP, contradicting the non-deterministic hierarchy theorem.

In the new paper, roughly speaking, Ryan scales back the result to simpler kinds of circuits, and derives his NEXP \not\subseteq ACC0 result from a faster-than-2^n algorithm to decide satisfiability of ACC0 circuits.

It was known that every function in ACC0 can be computed by a quasi-polynomial depth-2 circuit with AND gates connected to the inputs and feeding into a symmetric gate. (A symmetric gate is one whose output depends only on the number of ones in the input.) Ryan’s satisfiability algorithm works for this class of depth-2 circuits.

One (general) idea is that one can reduce the satisfiability question for a circuit of size m with n inputs to the satisfiability question for a circuit of size m' = m \cdot 2^k with n' = n-k inputs, for any k. Thus, if one could solve circuit satisfiability in time 2^{n'} + m' instead of m' \cdot 2^{n'} we would get a subexponential algorithm by picking k = n/2. Ryan shows that satisfiability of depth-2 circuits with AND gates at the bottom and a symmetric gate at the top can be solved in time 2^{n}\cdot poly(n) + m^{O(1)}, which suffices to derive a 2^{n - n^{\Omega(1)}} running time for ACC0 satisfiability.

The faster-than-trying-all-possibilities work is done by a fast algorithm for boolean matrix multiplication.

About these ads