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

Non Uniform ACC Circuit lower bounds by Ryan Williams

Ryan uses Nondet Hier

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

Time-Space Lower bounds for satisfiability

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:

BPP has subexp times imulations unless EXPTIME has publishable proofs

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.