# [CSS.303.1]

Algebraic Circuit Complexity

(2024, Aug–Dec)

**Schedule:** Tuesday, Thursday at 14:00 — 15:30 (IST)

## Problem sets and exams

## 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)
- (tentative) Existence of combinatorial designs, factors of small circuits have small circuits
- Lecture 22 (2024-11-19)
- (tentative)
- Lecture 23 (2024-11-21)
- (tentative)
- Lecture 24 (2024-11-26)
- (tentative) Succinct hitting sets and algebraic natural proofs
- Lecture 25 (2024-11-28)
- (tentative) A collection of open problems in this field

(Student presentations)