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. [mine]
- Geometric complexity theory. Eg. GCT Chasm. [link] [pdf]

Schedule.

[29-Jul week] Turing machines. Arithmetic circuits. Arithmetic complexity classes. [video1] [video2] [slide01]