CSC 2429 / MAT 1304: Circuit Complexity
Winter 2019

• Talk by Avishay Tal (Tuesday April 9, 3:10-4pm): Sparse Polynomial Approximations and their applications to Quantum Advantage, Parallel Computation, and Pseudorandomness

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⁰ (scribe: Dmitry Paramonov)
  
  
• Lectures 5-6: Lower bounds for AC⁰ and AC⁰[p] (slides)
  
  
• Lecture 7: AC⁰[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
  
  
  • Strassen's lower bound of Ω(n log d) for general arithmetic circuits (see Chapter 6 in this survey on lower bounds for arithmetic circuits)
  • Fast parallel algorithm for the symbolic determinant (Csanky 1975) and application to solving Bipartite Perfect Matching in randomized NC
    
    
• March 27: Guest lecture by Sasha Golovnev on Depth Reduction and Matrix Rigidity
  
  
  • Graph-theoretic arguments in low-level complexity (Valiant 1977)
  • Static data structure lower bounds imply rigidity (Dvir-Golovnev-Weinstein 2018)
  • Circuit depth reductions (Golovnev-Kulikov 2018)
    
    
• Plan for April 4 lecture: Branching Programs and the NC Hierarchy
  
  
  • Classes NC¹ ⊆ L/poly ⊆ NL/poly ⊆ SAC¹ ⊆ AC¹ ⊆ NC²
  • Barrington's Theorem: NC¹ = bounded-width branching programs
  • SAC¹ is closed under complementation (inductive counting)
  • Arithmetic setting: VP = VNC²

• 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]
  Hastad's switching lemma (§12.1-12.2)
  Lower bound for PARITY (§12.3)
  Approximation by low-degree polynomials (§2.6)
  Razborov-Smolensky lower bounds for AC0[p] circuits (§12.4-12.5)
  Depth-3 circuits (§11.1)
  
  
• Branching Programs
  Nechiporuk's lower bounds (§15.1, see also §6.5)
  Barrington's theorem (§15.4)