Circuit Complexity Now and Then

Spring 2014

ITCS @ IIIS, Tsinghua University
Instructor: Periklis A. Papakonstantinou []

Lectures: Monday 1.30-4.05pm (3x45min) and Monday 3.20-5.50pm (3x45min) (6 hours per week)

Remark: course starts on April 4th or March 31st (the instructor was on an academic visit)

Course requirement: one term-project at the level of a published paper in the field


Date     Topic
Jun 9 Razborov-Smolensky
and a list of everything else I wanted to cover but didn't
Jun 6 Worst-case to average-case reductions
Jun 2 Depth irreducibility and pseudo-random generators and implications to exponential circuit lower bounds
May 30 Non-uniform ACC0 and NEXP: 2nd part and open questions (lecture by Dominik Scheder)
May 26 Non-uniform ACC0 and NEXP: a very detailed presentation and discussion on Ryan Williams proof (lecture by Dominik Scheder)
May 23 Discussion, questions, and open problems lecture:
fixed size circuits and pseudo-randomness
May 19 Finishing up the details of Kabanets-Impagliazzo, remarks on the proof, and open questions
May 16 Derandomizing polynomial identity testing and circuit lower bounds:
a very detailed presentation and discussion (including all prerequisites) of Kabanets-Impagliazzo theorem, Impagliazzo-Kabanets-Widgerson theorem, and related theorems
May 12 Semi-unbounded circuits, the inductive counting for closure of SAC under complement, and open questions
May 8 The Nisan-Widgerson pseudorandom generator
Apr 28 Yao's XOR lemma
Apr 25 Introduction to derandomization (list of examples), and the hardness versus randomness paradigm
Apr 21 Monotone circuit lower bounds: Razborov and Alon-Boppana
Apr 18 AC0, ACC0: depth 2, depth 3, and depth 5 simulations
Apr 14 The switching lemma: statement, proofs, and applications
Apr 11 Discussion, questions, and open problems lecture:
the depth irreducibility hypothesis and its consequences, other depth vs size and simultaneous bounds conjectures and implications, the NC vs SC question, ATMs and uniformity, a list of questions for term projects
Apr 7 Max circuit size: Shannon and Lupanov (and their variants)
More on uniformity and circuit complexity
Apr 4 Cook-Levin, time and size, space and depth
Conjectures about simultaneous bounds: time-space vs size-depth
Mar 31 What is it about?
Circuits, algorithms, uniformity and some relations