SYLLABUS
topics (tentative).
- Basic algebra results, algorithms- Tensor rank (eg. matrix multiplication)
- Newton's identities, circuits, ABP (eg. determinant)
- Universality of depth-3 circuits, width-2 ABP
- 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. Egs. GCT Chasm. [link]
Schedule.
[14-Apr-2016] [pdf] ROABP quasipoly-prg. PIT for depth-3 (bounded fanin).
[12-Apr-2016] [pdf] Whitebox PIT for ROABP.
[07-Apr-2016] [pdf] PIT for tiny depth-3 suffices. Diagonal depth-3, set-multilinear depth-3, ROABP.
[05-Apr-2016] [pdf] PIT for tiny diagonal depth-4 suffices. Prg for depth-2 (or sparse).
[31-Mar-2016] [pdf] PIT and exponential lower bounds are equivalent (almost).
[29-Mar-2016] [pdf] PIT, hitting-sets, prgs and lower bounds.
[17-Mar-2016] [pdf] Exponential lower bound for homogeneous depth-4.
[15-Mar-2016] [pdf] Shifted partials of determinant. Exponential lower bound.
[10-Mar-2016] [pdf] Shifted partials of degree-restricted depth-4.
[08-Mar-2016] [pdf] Constant-depth multilinear. Multilinear formula.
[03-Mar-2016] [pdf] Measure lower bound for det, per. Constant-depth multilinear.
[01-Mar-2016] [pdf] Raz-Yehudayoff measure for multilinear depth-3.
[25-Feb-2016] [pdf] Measure lower bound for det, per, symm polynomials.
[23-Feb-2016] [pdf] Depth-3 over finite fields. Grigoriev-Karpinski measure.
[04-Feb-2016] [pdf] Width reduction. Formulas vs width-3. Width-2 Chasm.
[02-Feb-2016] [pdf] Interpolation. Using a basis of powers. Depth-3 Chasm.
[30-Jan-2016] [pdf] Nontrivial reduction to constant-depth.
[28-Jan-2016] [pdf] Circuit Depth Reduction: Frontier expansion.
[21-Jan-2016] [pdf] Circuit Depth Reduction: Frontier gates, Gate quotients.
[19-Jan-2016] [pdf] Partial derivatives. Formula depth reduction.
[16-Jan-2016] [pdf] Clow sequence via ABP. Homogeneous parts.
[14-Jan-2016] [pdf] ABP vs det. Det via clows.
[12-Jan-2016] [pdf] Arithmetic branching program, Iterated matrix multiplication, Determinant.
[07-Jan-2016] [pdf] Determinant in VP. Newton's identity.
[05-Jan-2016] [pdf] Arithmetic complexity classes. Valiant's VP, VNP.
[31-Dec-2015] [pdf] Turing machines. Arithmetic circuits.