A Circuit Lower Bound Breakthrough

Posted on by

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.

9 thoughts on “A Circuit Lower Bound Breakthrough”

  1. Point of clarification: he proves (the stronger result) that ACC does not contain NE, not NEXP, right?

  3. The two are equivalent. If ACC contained NE, it would also contain NEXP by
    padding.

  4. Hi Luca,
    I think that one critical point in Ryan’s beautiful work did not get enough attention: In order to apply Ryan’s technique, you don’t need a (weak) algorithm for deciding circuit satisfiability, but rather a (weak) algorithm for distinguishing an unsatisfiable circuit from a circuit that is satisfied by at least half of its assignments.

    The latter distinguishing problem is easily solvable within RP, and the point is that Ryan’s technique requires a weak *deterministic* algorithm.

    This fact is important for two reasons:
    1. It makes Ryan’s technique much stronger and more applicable, since it is much more plausible to find weak deterministic algorithms for an RP problem than to an NP-complete one (i.e. Circuit-Sat).

    2. More conceptually, I think that Ryan’s technique should be viewed as a very powerful instance of the family of “derandomization implies circuit lower bounds” results.

  5. This is a nice summary. Being picky:

    “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?.”

    Polynomial-size missing.

    “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.”

    I think this is not completely accurate. The satisfiability algorithm starts by taking an OR of a few restrictions of the original circuit and then applying the transformation to a depth-2 circuit with a symmetric gate at the root. The author himself mentions that his algorithm does not work directly on this class of circuits as it needs the closure under ORs.

  6. Why is NEXP of special significance in this result?

    It seems like there was another class in the exp-time hierarchy, MA-EXP, for which there were known lower bounds. How come that wasn’t celebrated?

    Is it because of the simple explicit problem SUCCINCT-SAT?

    HALTING is not in ACC too, right?

  7. I just read the answer to my question in the paper: lower bounds for general circuits for languages in NEXP imply derandomization of probabilistic complexity classes.

    The same is not true for lower bounds for general circuits for HALTING 🙂

  8. Pingback: How Ryan’s Circuit Lower Bound Works « Gödel’s Lost Letter and P=NP

  9. Pingback: Circuit Lower Bounds by Properties and by Brute Force « in theory

Leave a comment