# 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