# 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.