This is a collection of papers that are needed to understand Ryan Williams Lower Bound on Circuits.

*A Casual Tour around a Circuit Complexity Bound*by Ryan Williams SURVEY.PDF, SURVEY.PS.*Non Uniform ACC Circuit lower bounds*by Ryan Williams RYAN.PDF This is the full version of the paper.- Arora-Barak have a writeup here:
AB.PDF
(Scroll to the bottom.)
- Ryan uses the nondeterministic time hierarchy (if we really want to be
thorough) and the first half of his STOC'10 paper
RYANOLD.PDF.
This paper also talks about the next two items.
- 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
FLVV.PDF.
- 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
BFNW.PDF.
- 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
ACC.PS,
ACC.PDF.
- 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.