CSC 2429 / MAT 1304: Circuit Complexity
Winter 2019
ANNOUNCEMENTS:
Lectures: Thursdays 46, 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 AC^{0} (scribe: Dmitry Paramonov)
 Lectures 56: Lower bounds for AC^{0} and AC^{0}[p] (slides)
 Lecture 7: AC^{0}[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 NC^{1} ⊆ L/poly ⊆ NL/poly ⊆ SAC^{1} ⊆ AC^{1} ⊆ NC^{2}

Barrington's Theorem: NC^{1} = boundedwidth branching programs

SAC^{1} is closed under complementation (inductive counting)

Arithmetic setting: VP = VNC^{2}
Preliminary outline of topics
 Circuits as a Model of Computation
Boolean functions, the binary cube, CNFs and DNFs (§1.1, pages 310)
General circuits, formulas, DeMorgan circuits (§1.2, pages 1214)
Simulation of Turing machines by circuits
Derandomization of probabilistic circuits (§1.2, pages 1415)
 Counting, Gate Elimination
Circuit size of random boolean functions (§1.4, pages 2126)
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 79)
Razborov's lower bound for CLIQUE (§9.1)
Valiant's monotone formulas for MAJORITY
Slice functions (§10.1)
 AC0 and AC0[p]
Hastad's switching lemma (§12.112.2)
Lower bound for PARITY (§12.3)
Approximation by lowdegree polynomials (§2.6)
RazborovSmolensky lower bounds for AC0[p] circuits (§12.412.5)
Depth3 circuits (§11.1)
 Branching Programs
Nechiporuk's lower bounds (§15.1, see also
§6.5)
Barrington's theorem (§15.4)