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]
- 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.
- Geometric complexity theory. Eg. GCT Chasm. [link] [pdf]
Schedule.
[17Apr/ Abhibhav Garg] [pdf] Succinct hitting-sets.
[16Apr/ Extra] [pdf] Some polynomial identity tests.
[09,10,16Apr] [pdf] Polynomial identity testing vs. Lower bounds.
[13Mar, 02,03Apr] [pdf] Depth-4 lower bounds.
[05,06,12Mar] [pdf] Multilinear lower bounds-- constant-depth circuits; formulas.
[26,27Feb, 02Mar] [pdf] Lower bounds-- Depth-3 over finite fields.
[05,06,12,13Feb] [pdf] Reducing to depth-4, depth-3 or width-2. Approximative computing.
[23,29,30Jan, 05Feb] [pdf] Structures-- Homogenization, derivatives, log-depth reduction.
[16,22,23Jan] [pdf] Determinant vs Arithmetic Branching Programs (ABP).
[09,15Jan] [pdf] Determinant is in VP.
[08,09Jan-2019] [pdf] Turing machines. Arithmetic circuits. Arithmetic complexity classes.