A Breakthrough Result
A great result on circuit lower bounds
Ryan Williams is one of the top complexity theorists in the world, young or old. He has just released a draft of a result that moves us closer to understanding the mysteries of circuit complexity classes.
Today I want to give a short summary of what he has done, and how he did it. I think it is potentially the biggest, best, most brilliant—okay I really like his result.
The beauty of his result is that while the details are non-trivial it follows a schema that I believe could be used to solve other open problems. I think it could even solve
Ryan proves the following result:
Theorem: The nondeterministic time class does not have non-uniform circuits of polynomial size.
Actually he proves several other related theorems.
Note, the theorem shows a non-uniform lower bound. That is a breakthrough. Proving circuit lower bounds that allow non-uniformity is extremely difficult. Somehow the power of allowing the circuit to vary with the input size is very difficult for us to understand. For example, we still do not know if polynomial time is contained in linear size circuits—see my earlier discussion on this.
The Proof Schema
If you want to understand what Ryan has done see his paper. It is well written and explains the details in a clear and careful manner. What I will try to do is give a 50,000 foot view of the proof.
Make an Assumption: Ryan assumes, by way of contradiction, that has polynomial size circuits. Recall these are constant depth circuits that can have unbounded fan-in gates AND, OR, and any MOD gate for any .
Use The Assumption: He then proves that if circuit satisfiability can be solved faster than exhaustive search there is a contradiction. The contradiction is with the classic nondeterministic time hierarchy theorem. This part of the proof is based on his STOC 2010 paper, with an additional twist. He needs the assumption he made in order to prove the simulation step—that step cannot be proved unconditionally.
Break The Assumption: He then needs to show that the SAT problem restricted to circuits can be done slightly better than . But how do you beat the naive SAT algorithm for circuits? Ryan shows that he can beat it by a clever application of a clever algorithm: a special case of matrix multiplication. He uses the following beautiful result of Don Coppersmith:
Lemma: The product of an matrix with an matrix can be done in operations over any ring.
See his paper for the details. Wonderful.
Can Ryan’s results be improved? What happens if matrix product can be done faster? The last comment I will leave to Ryan:
“Improved exponential algorithms for satisfiability are the only barrier to further progress on circuit lower bounds for NEXP.”