Arithmetic Circuit Complexity

In this course we will study computation by primarily algebraic models, and use, or in many cases extend, the related tools that mathematics provides.We will start with some positive examples-- fast polynomial multiplication, matrix multiplication, determinant, matching, linear/algebraic independence, etc. The related tools are FFT (fast fourier transform), tensor rank, Newton's identity, ABP (algebraic branching program), PIT (polynomial identity testing), Wronskian, Jacobian, etc. One surprising result here is that certain problems for general circuits reduce to depth-3 circuits. Furthermore, the algorithmic question of PIT is related to proving circuit lower bounds.We then move on to proofs, or attempts to prove, that certain problems are hard and impossible to express as a small circuit (i.e. hard to solve in real life too). One such problem is Permanent. We study the hardness against restricted models-- diagonal circuits, homogeneous depth-3, homogeneous depth-4, noncommutative formulas, multilinear depth-3, multilinear formulas, read-once ABP, etc. The partial derivatives, and the related spaces, of a circuit will be a key tool in these proofs. The holy grail here is the VP/VNP question.Depending on time and interest, other advanced topics could be included. One such growing area is-- GCT (geometric complexity theory) approach to the P/NP question.INTENDED AUDIENCE : Intersted studentsPREREQUISITES : Preferable (but not necessary)-- Theory of Computation, Algorithms, AlgebraINDUSTRY SUPPORT : Cryptography, Coding theory, Symbolic Computing Software, Learning Software

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.