State of circuit lower bounds now slightly less humiliating

When people want to emphasize how pathetically far we are from proving P≠NP, they often use the following argument: for godsakes, we can’t even prove that NEXP-complete problems aren’t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates!

But no more.

As some of you may have heard, recently Ryan Williams achieved a breakthrough in circuit lower bounds.  And as a result, now we can prove that NEXP-complete problems aren’t solvable by depth-3, polynomial-size circuits consisting entirely of mod 6 gates.

More generally, Williams proves that NEXP does not have ACC circuits of third-exponential size: that is, size f(n) where f(f(f(n))) is exponential.  Here NEXP means nondeterministic exponential time (the exponential-time analogue of NP), and was long a “barrier class” for circuit lower bounds.  (Note that, if we go even slightly above NEXP, to MAEXP, then Buhrman, Fortnow, and Thierauf proved in 1998 that MAEXP doesn’t have polynomial-size circuits of any depth, and here the polynomial can be improved to half-exponential.)  Meanwhile, by “ACC circuits” we mean a nonuniform family of constant-depth circuits consisting of AND, OR, NOT, and MOD m gates for arbitrary positive integers m.  ACC is another “barrier class” for circuit lower bounds: if we go even slightly below it, to AC0[p] (the same as ACC, except that now we only allow MOD p gates for some fixed prime p), then we’ve known how to prove exponential circuit-size lower bounds since the work of Razborov and Smolensky in the 1980s.

To achieve the combination of NEXP and ACC, Williams implements a program proposed in his previous STOC’2010 paper, for the specific case of ACC.  At the core of his lower bound is an algorithm for deciding satisfiability of ACC circuits, which does slightly (not much) better than brute-force search.  (The algorithm relies on, of all things, fast multiplication of rectangular matrices.)  While Williams’s techniques have nothing to do with Mulmuley’s GCT program, they do fit in well with the Mulmuleyist “flip” philosophy of “proving lower bounds by proving upper bounds.”

I haven’t verified Williams’s proof, but the high-level ideas are compelling—and while the result is one of the most spectacular of the decade, it’s not so far beyond the current frontier as to strain credulity.  Suffice it to say that I won’t be betting $200,000 against this one. Congratulations, Ryan! Update: Amusingly, if you google Ryan Williams ACC, you get a football player of the same name who was apparently Rookie of the Year in the Atlantic Coast Conference. Let’s all link to Ryan’s paper from our homepages, and see if we can make our “ACC Rookie of the Year” win out! 34 Responses to “State of circuit lower bounds now slightly less humiliating” 1. RubeRad Says: And I bet he typeset his result in LaTeX too… 2. Scott Says: Indeed he did 😉 3. Jill Says: And as luck would have it he is on the job market this year! Need any more complexity theorists at MIT? 4. Scott Says: Jill: Personally, I think it’s obvious that any department that gets Ryan and Virgi will have scored a coup. But I’d like to issue a polite request to refrain from further job-market discussion on this thread. Even if they start out with good intentions, comment threads about the academic job market have shown a reliable, Godwin-like tendency to turn nasty and trample on people’s privacy. 5. NCLM Says: What exactly is third-exponential size? Could you give an example function? 6. Scott Says: NCLM: As I said, “third-exponential” means a function f such that f(f(f(n))) grows like 2n. Unfortunately, while such functions can be proved to exist, they don’t have any closed form in terms of familiar functions like exp, log, etc. — otherwise, I would’ve used the closed form! 🙂 These sorts of functions (more typically “half-exponential,” meaning that f(f(n)) grows like 2n) have come up before in circuit lower bounds. In fact, I had a whole comment thread about them a few years back. 7. Bram Cohen Says: Scott, is there a function expressible in closed form using the familiar functions which is between third-exponential and half-exponential? Can we prove that NEXP-complete problems aren’t solvable by logarithmic depth, polynomial-size circuits consisting entirely of mod 6 gates, or is that another huge hurdle? Does this result cross some relativization/naturalization/algebrization barrier, or is it still below those? 8. Scott Says: Bram: is there a function expressible in closed form using the familiar functions which is between third-exponential and half-exponential? I doubt it—but alas, I don’t know how to prove that any such function is not expressible in closed form. This is what I was asking about in that thread from years ago, and I never got an answer. Maybe I’ll post the question to MathOverflow! Can we prove that NEXP-complete problems aren’t solvable by logarithmic depth, polynomial-size circuits consisting entirely of mod 6 gates, or is that another huge hurdle? Another huge hurdle. Does this result cross some relativization/naturalization/algebrization barrier, or is it still below those? Yes, I think it crosses the relativization and algebrization barriers, in the sense that one can construct an oracle A relative to which NEXPA ⊆ ACCA, and even NEXP~A ⊆ ACCA (this should follow from trivial modifications to the NEXP~A ⊆ PA/poly oracle from my paper with Wigderson). As for the natural proofs barrier, the issue is that we don’t currently have a good candidate for a pseudorandom function family (PRFF) computable by ACC circuits. Indeed, maybe Ryan’s new algorithm for ACC circuit satisfiability could be used to show that no such PRFF can be “maximally hard to break”! On the other hand, if there is a natural proofs barrier for ACC, then Ryan’s proof certainly gets around it—which would be no great surprise, since the proof ultimately relies on a time hierarchy theorem, and time hierarchy theorems are the “original” non-naturalizing lower bounds! 9. asdf Says: One of the most spectacular of WHICH decade? 2001-2010 I guess? Just making sure. 🙂 NCLM and Bram: http://en.wikipedia.org/wiki/Functional_square_root says a little bit. 10. Scott Says: asdf: Yeah, I meant the preceding decade, which is the one I know somewhat more about. Here’s hoping that complexity theory (and esp. circuit lower bounds) in the next decade will surpass this result! 11. Mitchell Porter Says: Scott wrote: ‘The algorithm relies on, of all things, fast multiplication of rectangular matrices… While Williams’s techniques have nothing to do with Mulmuley’s GCT program, they do fit in well with the Mulmuleyist “flip” philosophy of “proving lower bounds by proving upper bounds.”’ There may be more than a philosophical connection! Geometric methods have already been employed to study the complexity of matrix multiplication (arxiv:cs/0703059), and GCT specifically is just beginning to be used there (arxiv:1011.1350). 12. oz Says: As an outsider to complexity theory who can more or less understand the statement in William’s result (but far from being able to understand the proof) – if you define a metric where 1 is the size of a breakthrough on the order of William’s, and the distance X is the number of breakthroughs of similar magnitude required to get from state of knowledge A to state of knowledge B (say each of them have a different known lower bound) – what is the distance X from our current state of knowledge to figuring out if P≠NP? 13. Scott Says: oz: 587. 14. Bram Cohen Says: Scott: I’m not sure my question was worded clearly – Do you know of an ordinary function which is asymptotically greater than third exponential but asymptotically less than half exponential? The lack of difficult functions in ACC confuses me. Aren’t these the sorts of things which block ciphers are generally made out of? You can even cheat a bit and do diffusion using gates with large fan-in. Then again, the number of rounds of a black cipher is generally significant, so maybe that’s where the log(n) sneaks in. Maybe Williams’s new technique could be applicable to breaking ciphers. If block ciphers really are just barely not possible in ACC, than next barrier is a real doozy. Since you say that this is the biggest result since at least 2000, and that there are 587 left to go, does that mean that you think it will be at least 5870 * 11 = 64570 years until we can prove that P != NP? 15. Bram Cohen Says: sorry, I meant 587 * 11 = 6457 years, dunno how that typo happened 16. Scott Says: Good news, everyone! I posted the question to MathOverflow of whether one can prove that there’s no closed-form formula (using the operations +, -, *, /, exp, and log) for a function f such that f(f(n)) grows exponentially. I got an immediate positive answer from Gerald Edgar. Note that this result also holds for third-exponential functions, etc., as well as (for example) anything sandwiched between third- and half-exponential. So we have an answer to Bram’s question above: no, there are no “natural” functions with any of these growth rates—at least if by “natural”, you mean definable by composing various functions with “ordinary” growth rates! 17. Bram Cohen Says: There really is a giant no man’s land between polynomial and exponential! 18. Scott Says: Bram, to address your other question: we don’t know whether or not there are good pseudorandom functions in ACC. (By contrast, if you just wanted pseudorandom generators, which stretch the seed by a polynomial rather than an exponential amount, then we can certainly get that in ACC, and even in much smaller classes like NC0.) Especially in the wake of Ryan’s result, the question of whether ACC has pseudorandom functions seems extremely well worth answering. The answer will determine whether (a) Ryan’s lower bound circumvents the Natural Proofs barrier, or (b) ACC never had a Natural Proofs barrier to begin with. (In other words, this problem is sort of like figuring out whether the front door was locked, after the barbarians have already stormed the castle… 🙂 ) 19. Bram Cohen Says: A sub-exponential algorithm for figuring out if an ACC circuit is satisfiable would be quite a surprising result! 20. anon Says: Google for: Ryan Williams acc0 It seems that dropping that 0 has a significant effect and we should keep it even if it does not make sense. 😉 21. anon Says: The Wikipedia page for Ryan Williams should be updated, otherwise I am not optimistic that we can change the ranking by linking to Ryan’s page. 22. Raoul Ohio Says: Re: Half exponential in closed form. A solution in closed form means exactly that it is expressible in terms of some function that has a name, nothing more or less. If the name has some tradition, or appears in a book or list, so much the better. Back in the day, this meant it was covered in, say, Abramowitz & Stegun, or maybe Magnus & Oberhettinger. Nowadays, maybe being in MS Excel, or the Boost C++ special functions package, or Mathematica, or maybe if Google evaluates it, resonates. With no further ado, I hereby define a sequence of “fractional exponential” functions by the functional equations e(1, x) = 2^x, e(2, e(2, x)) = 2^x, e(3, e(3, e(3, x))) = 2^x, e(4, e(4, e(4, e(4, x)))) = 2^x, and so on. If you put your pure mathematician hat on, figure out if these are defined uniquely. If you put your applied mathematician hat on, figure out some properties of these functions. For example, e'(2, x) = ln 2 e(1, x) / e'(2, e(2, x)). That is a start. You are on your own now. As I recall, when Scott asked about e(2,x) a few years ago, I figured out some properties. I don’t recall if I sent them in. BTW, M&E is still selling for about$50 on Amazon. I have one up in the attic. A&S now has an improved online version at http://dlmf.nist.gov/ Check it out! As with the Ackermann function, as a matter of principal everyone should know a little bit about the Riemann Zeta function.

23. Joshua Zelinsky Says:

Raoul, those aren’t satisfactory answers. When people want closed form functions they generally are asking for an elementary function.

24. LifeIsChill Says:

How far away is the community now from proving $P \ne NP$. Is any kind of proof visible at this stage?

25. Scott Says:

Is any kind of proof visible at this stage?

26. Or Meir Says:

Hi,
I think that one critical point in Ryan’s beautiful work is not emphasized enough: 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.

Note that 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 believe that Ryan’s technique should be viewed as a very powerful instance of the family of “derandomization implies circuit lower bounds” results. Perhaps other techniques from this family can be combined with Ryan’s work to obtain even stronger results.

27. Raoul Ohio Says:

Joshua,

Functions are generally classified as:

1. Elementary: What you wind up with if you start with polynomials, exponentials, and logs, and apply +, -, *, /, and root finitely many times. These are in a standard calculus book.

2. Algebraic: Satisfies a polynomial equation, whose coefficients are polynomials in x (the independent variable).

3. Transcendental: Not algebraic. Note that some elementary functions are Algebraic (polynomials, rationals, fractional powers), and some Transcendental (trig, logs, irrational powers).

4. Higher Transcendental: Many references (29 hits on Amazon) have this title. Usually the gamma function is regarded as the “lowest of the higher transcendental” functions, and is Chapter 1.

5. Functions of Mathematical Physics and/or Special functions (441 hits on Amazon): A subset of the Higher Transcendentals that turn up a lot in physics, usually as a result of using separation of variables on the wave, potential, and heat equation in two or three dimensions.

6. Hypergeometric (possibly generalized and/or confluent). An astounding fraction of important functions fit into a simple framework created by Gauss. If you work with them, everything falls into place, and you realize what a sharp guy Gauss was.

Over 100 years ago it was realized that most solutions to ordinary differential equations do not fall into any category of of known functions. All you can do is name the solution, and set to work figuring out some properties and working out suitable approximations. You can do a good job at this; last week a space probe zipped past and photographed a comet that looks like a bowling pin. It was not an accident that it was near by, it was engineers approximating differential equations.

The only thing you know about the half exponential function is that f(f(x)) = 2^x. This probably does not define it uniquely. A pure math question is how smooth a solution there is. At any rate, this is a hard equation to learn much from, and it is a good bet that the solution will be “more transcendental” that the solutions you get from simple differential equations.

So, the likelihood that there is an “elementary solution” is pretty close to 0.0. That just means it is time to figure out some properties. A few power series coefficients at x=0 would be interesting. For TCS purposes, an decent approximation for large x would be almost as good as an explicit formula. For example, a reasonably simple pair of functions g and h such that for large x:

x WLT g(x) LT f(x) LT h(x) WLT 2^x,

(WLT = Way Less Than, LT = Less Than)

would be useful.

28. Joshua Zelinsky Says:

Raoul, yes, thank you I knew that. Note that in his post on Math Overflow, Scott apparently interpreted closed form essentially as I did.

29. matt Says:

Just wanted to point out to everyone that there is a typo in Scott’s answer of 587 above. He forgot the exponent, the right answer is 10^587…. 🙂

(not taking anything away from Ryan, but rather to give to a different problem)

30. Raoul Ohio Says:

How about a closed form function that shares some key aspects of a half exponential? Perhaps a simple function f(x) that is is subexponential (i.e., limit f(x) / 2^bx = 0 for any b>0, limit is at infinity) and also limit f(f(x)) / 2^x is greater than 1.

The simplest one I could come up with is

f(x,a) = x^(x^a) for any a in (0,1).

g(x) = x^(lg x) does not work, because g(g(x)) is still subexponential, in fact x^(lg x)^3.

31. Raoul Ohio Says:

Switching from x to n for the variable, we look for the half exponential h(n), defined by h(h(n)) = 2^n.

Recall that exponent towers are evaluated from the top down, thus

g(n) = n^(lg n) = 2^(lg n)^2,

g(g(n)) = 2^(lg n)^2^2,

and in general an m-times iterated g(n) is given by

g(g(g( ….g(n)…) = 2^(lg n)^2^m = n^(lg n)^(2^m -1).

It is pretty surprising to find a simple expression for an iterated function!
However,

2^(lg n)^p and n^(lg n)^p

are subexponential for any power p, as can be seen by dividing by 2^dn for any positive d, so this family of functions is too small to contain h(n).

If h(n) is written as h(n) = n^k(n), the above results show that

(lg n)^p for any p is a lower bound and n^a is an upper bound for any positive a, giving hope of finding a k(n) that somehow interpolates between (lg n)^p and n^a. Means and geometric means do not work in the n go to infinity limit.
If I get some time and a pot of ultra strength coffee this weekend, I am going to try the family

k(n,b,c) = n^(b/n^c) for positive b and c.

The idea is to be less than n^a in the limit. If there are values of b and c such that h(n,b,c)= n^k(n,b,c) is subexponential, but h(h(n,b,c),b,c) is exponential, we would be pretty close to pinning down h(n).

First I need to work out the algebra of exponent towers.

32. jonas Says:

To matt: the proof for P ne NP would be 587 times as long as the current ones, but finding it requires 10^587 times as much computation.

33. Sniffnoy Says:

Basic question: Reading about this, some places I’ve seen ACC defined so that each circuit can only use mod m gates for a fixed integer m; other places have not mentioned any restriction against using different moduli in the same circuit. So – is the latter equivalent to the former? If not, is the latter something that’s been studied at all?

34. eli Says:

Do we know $NP$ is not in $ACC0$? If $NP$ is in $P/poly$ but the circuit needs to be only of $ACC0$ structure would that mean $NP$ is in $P/poly$ as well?