Arithmetic Circuit Complexity

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 equivalentWeek 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.