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.
Thanks to the support from MathWorks, enrolled students have access to MATLAB for the duration of the course.