Reading Group on Circuit Lower Bounds - Spring 2012

Here is the tentative syllabus for the reading group.

Date Speaker Title/Abstract
March 14, 2012 Igor Shinkar Basic definitions + some simple examples, basically covering chapter 2 in The Complexity of Finite Functions

March 21, 2012 Shlomo Jozeph Hastad's Switching Lemma. Can be found in A Switching Lemma Primer of Paul Beame.

March 26, 2012 Ryan Williams Non-Uniform ACC Circuit Lower Bounds of Ryan Williams

April 18, 2012 Avishay Tal Razborov-Smolensky result saying that PARITY is not in AC_0[3]

May 2, 2012 Elazar Goldenberg The paper of Linial, Mansour and Nissan "Constant Depth Circuits, Fourier Transform, and Learnability". The paper of Boppana "The average sensitivity of bounded-depth circuits".

May 9, 2012 Gil Cohen The paper of Mark Braverman "Poly-logarithmic independence fools AC0 circuits".

May 16, 2012 Daniel Reichman Lower bounds for clique in monotone circuits of Razborov/Alon-Boppana. Can be found in The Complexity of Finite Functions.

May 23, 2012 Rani Izsak A result of Valiant saying that Majority can be computed by monotone circuits of polynomial size and logarithmic depth.

May 30, 2012 Inna Polak A result of A. Haken "Counting Bottlenecks to Show Monotone P != NP". It gives an alternative proof the result of Razborov we've seen two weeks ago.

June 13, 2012 Tal Wagner "Bounded-depth circuits cannot sample good codes" of Lovett and Viola.

June 20, 2012 Ilan Komargodski Some results related to boolean formulas. Chapter 6 in Jukna's book.

July 4, 2012 Tom Gur Some results on arithmetic circuits. He will talk about "Lower bounds on arithmetic circuits via partial derivatives" [Nisan, Widgerson], and mostly about "Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size" [Raz]

July 11, 2012 Eylon Yogev A construction of a monotone bounded depth circuit for the k-Clique problem in G(n,p). Chapter 5 from Rossman's thesis

July 18, 2012 Ron Rothblum Natural Proofs

July 25, 2012 Igor Shinkar Lower bound for monotone circuits for the k-Clique in G(n,p). Chapter 4 from Rossman's thesis