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.
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!