next up previous
Next: About this document ...

RYAN WILLIAMS LOWER BOUND ON CIRCUITS

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

  1. A Casual Tour around a Circuit Complexity Bound by Ryan Williams SURVEY.PDF, SURVEY.PS.

  2. Non Uniform ACC Circuit lower bounds by Ryan Williams RYAN.PDF This is the full version of the paper.

  3. Arora-Barak have a writeup here: AB.PDF (Scroll to the bottom.)

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

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

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

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

  8. We'll need Beigel-Tarui representation of ACC as quasi-polynomial size SYM of ANDs. The paper is ACC.PS, ACC.PDF.

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

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




next up previous
Next: About this document ...
William Gasarch 2011-10-07