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
|