CS748 - Arithmetic Circuit Complexity (Sem II, 2018-19)


Instructor: Nitin Saxena

TAs: Sumanta Ghosh

Office: RM 203

Lectures: Tue (12-13:15), Wed (12-13:15); Studio M-12 in Media Technology Center

Office Hours: TBA

Email: nitin [at] iitk . ac . in


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.

Prerequisites: Theory of Computation, Algebra.

Text Book:  - Contemporary research papers and survey articles.
                    - Algebraic Complexity Theory. Authors: B├╝rgisser Peter, Clausen Michael, Shokrollahi Amin


  Course begins on Tue, 08-Jan-19.