Topics in Complexity Theory

• Instructors : Neeraj Kayal and Chandan Saha   Course number and Credits : E0 309 and 3:1   Lecture time : M,W 3:30-5 pm   Venue : CSA 117


• Objective : The theme of the course in this semester is arithmetic circuit complexity. Arithmetic circuits are algebraic analogue of boolean circuits that naturally compute multivariate polynomials. The quest for a thorough understanding of the power and limitation of the model of arithmetic circuits (and its connection to boolean circuits) has lead researchers to several intriguing structural, lower bound and algorithmic results. These results have bolstered our knowledge by providing crucial insights into the nature of arithmetic circuits. Still, many of the fundamental questions/problems on arithmetic circuits have remained open till date.The aim of this course is to provide an introduction to this area of computational complexity theory. We plan to discuss several classical and contemporary results and learn about a wealth of mathematical (particularly, algebraic and combinatorial) techniques that form the heart of this subject.


• Grading policy :
  • Paper presentations - 60%
  • Scribing lecture notes - 40%


• Lectures (unedited notes scribed by students):
  • Lecture 1: Introduction; Karatsuba's multiplication algorithm; A lower bound
  • Lecture 2: Polynomial multiplication; Matrix Vector multiplication; Fast Fourier Transform
  • Lecture 3: Matrix multiplication; Tensors and tensor rank
  • Lecture 4: Parallel computation; Integer addition in AC0
  • Lecture 5: Integer multiplication not in AC0; Iterated Integer addition and multiplication in TC0
  • Lecture 6: Determinant and rank in NC
  • Lecture 7-8: GCD computation; Bipartite matching
  • Lecture 9: Some known results on circuit lower bounds
  • Lecture 10: Irreducibility of Determinant; Lower bounds for random functions/polynomials
  • Lecture 11: Diagonal depth-3 circuits: upper and lower bounds
  • Lecture 12: Diagonal depth-3 circuits: upper and lower bounds (contd.)
  • Lecture 13: Basics of monomial ordering
  • Lecture 14: Homogeneous depth 3 lower bound for determinant
  • Lecture 15-16: Homogeneous depth 3 lower bound for symmetric polynomials
  • Lecture 17-18: (Student presentations) Determinant is complete for Algebraic Branching Programs (Ref: This paper by Mahajan and Vinay)
  • Lecture 19-20: (Student presentations) Lower bounds for non-commutative computation (Ref: This paper by Nisan)
  • Lecture 21-24: (Student presentations) Tensor-rank and lower bounds for arithmetic formulas (Ref: This paper by Raz)