RYAN WILLIAMS LOWER BOUND ON CIRCUITS
This is a collection of papers that are needed to understand
Ryan Williams Lower Bound on Circuits.
What Succinct3SAT is, and why it's got a very tight NP-hardness reduction.
There are several references where one can rederive the result from
the reference: Cook’88, Robson’91, Tourlakis, Gurevich and Shelah.
But those references just talk about the NP-completeness of SAT… the
key property we need (that each bit of the SAT reduction can be
computed in poly(log n) time) was observed by Fortnow, Lipton, Van
Melkebeek, and Viglas:
which is
Why NEXP in Ppoly implies that satisfying assignments for
Succinct3SAT can be encoded with polynomial size circuits.
The primary background needed here is Impagliazzo, Kabanets, and
Wigderson, which in turn uses results from derandomization such as
Nisan-Wigderson. Filling all the background needed here would probably
take too many lectures (Russell did it when he taught the ACC lower
bound at UCSD, and it took the whole quarter). Basically you need
EXP in Ppoly implies EXP=MA which is by
Babai-Fortnow-Nisan-Wigderson and is:
We will need results on derand of MA; however,
If we just wanted to prove lower bounds for EXP-to-the-NP, all this
background is not needed – there is an argument in the paper.
We'll need Beigel-Tarui representation of ACC as quasi-polynomial size SYM of ANDs.
The paper is
A baby-step towards Beigel-Yao would be to show that AC0 can be represented as a SYM of
ANDs, using polynomial tricks. It might be helpful to prove Toda's theorem first (or look at Toda's
theorem), because the techniques are similar.
A multilinear n-variate polynomial given in its coefficient
representation can be evaluated on all 2-to-the-n points in {0,1} to the n in 2 to the n
poly(n) time.