[CSS.303.1]
Algebraic Circuit Complexity
(2024, Aug–Dec)
Schedule: Tuesday, Thursday at 14:00 — 15:30 (IST)
Problem sets and exams
Resources
Lecture summary
- Lecture 1 (2024-08-22)
- Administrivia, introduction to the course, rough course outline, introduction to polynomials, computational models, basic properties.
- Lecture 2 (2024-08-27)
- Formal definition of classes VP and VNP, homogenisation of circuits, interpolation, efficient depth-3 circuits for elementary symmetric polynomials
- Lecture 3 (2024-08-29)
- Reductions and completeness, algebraic branching programs, reducing formulas and ABPs to determinants, depth reduction for formulas
- Lecture 4 (2024-09-03)
- Baur-Strassen’s lower bound for general circuits, extracting homogeneous components, division elimination, circuit for determinant via Gaussian elimination
- Lecture 5 (2024-09-05)
- Towards depth reduction for general circuits - introduction to gate quotients and frontier equations
- Lecture 6 (2024-09-10)
- Parse trees and reinterpreting gate quotient equations, depth reduction for general circuits, sketch of depth reduction to depth-4 circuits
- Lecture 7 (2024-09-12)
- Details of the Agrawal-Vinay depth reduction to depth-4 circuits, VSBR/AV preserves syntactic restrictions, Ben-Or and Cleve’s upper bound for formulas
(No lectures on 17th and 19th September 2024.)
- Lecture 8 (2024-09-24)
- Introduction to lower bound methods, sparsity as a complexity measure, Jerrum-Snir’s lower bound for monotone models, dimension of partial derivatives and application to Waring rank and homogeneous depth-3 lower bounds
- Lecture 9 (2024-09-26)
- The partial derivative matrix / communication matrix, set-multilinear circuit ABPs and read-once oblivious ABPs, Nisan’s characterisation of ROABP size
- Lecture 10 (2024-10-01)
- Rank of communication matrix under a random partition, application to lower bounds for multilinear models via relative-rank
- Lecture 11 (2024-10-03)
- Log-product decompositions and Raz’s lower bound for multilinear formulas, Dyck polynomials and separation between multilinear circuits and formulas
- Lecture 12 (2024-10-08)
- Limaye-Srinivasan-Tavenas’ lower bounds for constant depth circuits - I
- Lecture 13 (2024-10-11)
- Limaye-Srinivasan-Tavenas’ lower bounds for constant depth circuits - II
(No lectures on 15th and 17th October 2024.)
- Lecture 14 (2024-10-22)
- Forbes’ extension of the Limaye-Srinivasan-Tavenas lower bound for all fields, Gupta-Kamath-Kayal-Saptharishi depth reduction to depth-3 over large characteristic fields
- Lecture 15 (2024-10-24)
- Introduction to border-complexity, surprising power of border of depth-3 circuits of top fan-in 2, ROABPs are closed under taking border
- Lecture 16 (2024-10-29)
- Polynomial identity testing - whitebox and blackbox algorithms, Klivans-Spielman hitting sets for sparse polynomials, quasipolynomial hitting sets for depth-3 powering circuits
- Lecture 17 (2024-11-05)
- Quasipolynomial hitting sets for depth-3 powering circuits (completing the discussion), Raz-Shpilka’s polynomial-time whitebox PIT for ROABPs
- Lecture 18 (2024-11-07)
- Coefficient spans of ROABPs, rephrasing the Raz-Shpilka whitebox PIT using coefficient spans, rank extractors of Gabizon-Raz
- Lecture 19 (2024-11-09)
- Forbes-Shpilka’s quasipolynomial blackbox PITs for ROABPS, revisiting hitting sets for depth-3 powering circuits using Shpilka-Volkovich generators, even better hitting sets for depth-3 powering circuits.
- Lecture 20 (2024-11-12)
- Hitting sets to lower bounds (Heintz-Schnorr), combinatorial designs, towards hitting sets from lower bounds (Kabanets-Impagliazzo)
- Lecture 21 (2024-11-14)
- Existence of combinatorial designs, parameter settings for Kabanets-Impagliazzo Theorem, introduction to newton iteration for solving a system of polynomial equations
- Lecture 22 (2024-11-19)
- Chow-Kumar-Solomon’s proof that factors of small circuits have small circuits
- Lecture 23 (2024-11-21)
- Quadratic convergence in Newton Iteration without divisions, Factor conjecture, and Burgisser’s theorem (Factor conjecture is true in the border)
- Lecture 24 (2024-11-26)
- Succinct hitting sets and algebraic natural proofs
(Student presentations)