SYLLABUS
topics (tentative).
- Basic algebra results, algorithms- Newton's identities, circuits, ABP (eg. determinant)
- Homogenization, Derivatives, Depth reductions
- Universality of depth-3 circuits, width-2 ABP, approximative
- Homogeneity (tool- shifted partials)
- Multilinearity (tool- partials & rank-concentration)
- PIT (eg. matching, primality)
- Circuit lower bounds vs. PIT
- Depth-3 PIT results
- Noncommutativity (tool- partial derivative matrix)
- Diagonal circuits
- Read-once ABP
Advanced topic ideas.
- Equivalence of multivariate factoring and the identity testing problem. [pdf]- Tensor-rank and lower bounds for arithmetic formulas. [pdf]
- Exp.size lower bounds for constant-depth circuits (by Limaye-Srinivas-Tavenas'21) [pdf]
- Wronskian, Jacobian (eg. linear/ algebraic independence)
- Read-k ABP
- Bipartite matching in Quasi-NC
- Linear/ algebraic independence over finite fields
- Papers from the last 5-10 years. [mine]
- Geometric complexity theory. Eg. GCT Chasm. [link] [pdf]
Schedule.
[04-Nov week] PIT algorithms for assorted models: Diagonal depth-3. ROABP (or noncommutative ABP). Bounded top-fanin depth-3. [no videos] [slide10]
[28-Oct week] Hitting-set generator (hsg). Hardness to hsg. [video23] [video24]
[21-Oct week] Shifted-partials. Homogeneous depth-4. Polynomial identity testing. [video21] [video22] [slide09]
[14-Oct week] Degree-restricted depth-4. Shifted-partials rank measure. [video19] [video20] [slide08]
[30-Sep week] Coeff.matrix rank measure. Constant-depth multilinear circuit lower bounds. [video17] [video18]
[23-Sep week] Exp.Lower bound mod p. Multilinear model and its measure (coeff.matrix rank). Constant-depth multilinear circuit lower bounds. [video15] [video16] [slide07]
[09-Sep week] Flatten to depth-3, mod p? Exp.Lower bound results. [video13] [video14] [slide06]
[02-Sep week] Flattening to depth-3. Reducing ABP-width: to width-3; and, to width-2. Approximative model: Formula = ABP-width-2. [video11] [video12]
[26-Aug week] Depth-reduction. Flattening to depth-4; and, to depth-3. [video9] [video10] [slide05]
[19-Aug week] I- & II-order Derivatives. Depth-reduction for formula and circuit. [video7] [video8]
[12-Aug week] Determinant = IMM = ABP. Homogenization. Derivatives. [video5] [video6] [slide04]
[05-Aug week] Determinant is in VP. Algebraic branching programs (ABP). [video3] [video4] [slide02] [slide03]
[29-Jul week] Turing machines. Algebraic circuits. Algebraic complexity classes. [video1] [video2] [slide01]