Wednesday, November 05, 2014

Favorite Theorems: Circuit Lower Bounds

My long time blog readers should have no surprise on my final favorite theorem of 2005-2014.
Nonuniform ACC Circuit Lower Bounds by Ryan Williams (PDF)
We saw several exciting circuit lower bound results in the 80's, highlighted heavily in my first list of favorite theorems (1985-1994 sections 2.2 and 2.3). Progress happened so fast that many expected a proof that an NP-complete problem didn't have polynomial-size circuits, and thus P ≠ NP, was just around the corner. But after 1987 that progress came to a sudden stop. We saw some lower bounds for algebraic circuits or circuits of very small depth but no general lower bounds until the work of Ryan Williams.

For years I would point out that our limited knowledge of lower bounds allowed that possibility that NEXP could be computed by constant depth circuits with Mod6 gates. Williams eliminated that possibility for constant depth circuits with Modk gates for any k.

One could take the techniques and results that Williams uses in his paper and build a whole graduate computational complexity course on them. Dick Lipton did exactly that at Georgia Tech a couple years back.

Ryan Williams' greatest insight though was to find non-trivial satisfiability algorithms for ACC0 circuits and use them to give lower bounds for NEXP. Recently Ryan has turned that process around, for example getting a faster algorithm for all-pairs shortest path using the techniques from the Razborov-Smolensky circuit lower bounds. Ryan's publication page has several new results giving algorithms from lower bounds.

1 comment: