# CSC 2429 / MAT 1304: Circuit Complexity Winter 2019

ANNOUNCEMENTS:
Lectures: Thursdays 4-6, Bahen B026

Instructor: Benjamin Rossman

Office hours: by appointment

Textbook: Stasys Jukna "Boolean Function Complexity". Available to UofT students here (follow either link to Scholars Portal Books or SpringerLINK eBooks)

Background: Make sure you are comfortable with basic probability theory as presented in appendix §A.1.

Workload: Students are expected to attend lectures and encouraged to ask questions. Problems will be assigned during lectures; once or twice during the semester, a subset of these problems will make their way onto official problem sets (assigned at least a week in advance). Volunteers will be sought to scribe lectures on material outside the textbook.

Lecture notes from other courses: Allender, Buss, Kopparty, Servedio, Williams, Zwick

HOMEWORK PROBLEMS (updated March 6). You are asked to submit solutions to your choice of six problems on this list by the end of the term.

Lecture notes

• Lecture 1: DeMorgan circuits and formulas (scribe: Lily Li)

• Lecture 2: Gate elimination and formula lower bounds

• Lecture 3: Andreev's function, Nechiporuk's method, and BPP ⊆ P/poly

• Lecture 4: Valiant's monotone formulas for majority, overview of AC0 (scribe: Dmitry Paramonov)

• Lectures 5-6: Lower bounds for AC0 and AC0[p] (slides)

• Lecture 7: AC0[p] and approximation by real polynomials

• Lecture 8: Monotone circuit lower bounds (scribe: Bruno Pasqualotto Cavalar)

• Lecture 9: Monotone circuit lower bounds, continued

• March 21: Guest lecture by Mrinal Kumar on Arithmetic Circuit Complexity

• March 27: Guest lecture by Sasha Golovnev on Depth Reduction and Matrix Rigidity

• Plan for April 4 lecture: Branching Programs and the NC Hierarchy

• Classes NC1 ⊆ L/poly ⊆ NL/poly ⊆ SAC1 ⊆ AC1 ⊆ NC2
• Barrington's Theorem: NC1 = bounded-width branching programs
• SAC1 is closed under complementation (inductive counting)
• Arithmetic setting: VP = VNC2
Preliminary outline of topics
• Circuits as a Model of Computation
Boolean functions, the binary cube, CNFs and DNFs (§1.1, pages 3-10)
General circuits, formulas, DeMorgan circuits (§1.2, pages 12-14)
Simulation of Turing machines by circuits
Derandomization of probabilistic circuits (§1.2, pages 14-15)

• Counting, Gate Elimination
Circuit size of random boolean functions (§1.4, pages 21-26)
3n lower bound for PARITY (§1.6)

• Formulas
Size versus depth (§6.1)
Random restrictions (§6.3)
Nearly cubic lower bound for Andreev's function (§6.4)
Khrapchenko's theorem (§6.8)

• Monotone Circuits
Monotone functions, minterms and maxterms (§1.1, pages 7-9)
Razborov's lower bound for CLIQUE (§9.1)
Valiant's monotone formulas for MAJORITY
Slice functions (§10.1)

• AC0 and AC0[p]