Arithmetic Circuit Complexity Training

Week 1 : Turing machines. Arithmetic circuits.

Week 2 : Newton’s identity. Arithmetic branching program. Iterated matrix multiplication.

Week 3 : Arithmetic branching program vs. Determinant.

Week 4 : Circuit Depth Reduction.

Week 5 : Nontrivial reduction to constant-depth.

Week 6 : Width reduction.

Week 7 : Depth-3 over finite fields. Grigoriev-Karpinski measure.

Week 8 : Raz-Yehudayoff measure for multilinear depth-3.

Week 9 : Shifted partials of degree-restricted depth-4.

Week 10: Exponential lower bound for homogeneous depth-4.

Week 11: Polynomial Identity Testing (PIT) and exponential lower bounds are equivalent

Week 12: PIT for tiny depth-3 (or many other tiny models) suffices.

Thanks to the support from MathWorks, enrolled students have access to MATLAB for the duration of the course.