IIT Kanpur · Computer Science

Arithmetic Circuit Complexity

Prof. Nitin Saxena · 24 free video lectures

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…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 1: Turing Machines and Introduction to Arithmetic Circuits
  2. Lecture 2: Arithmetic complexity classes
  3. Lecture 3: Determinant is in VP
  4. Lecture 4: Determinant vs Arithmetic Branching Programs (ABP)
  5. Lecture 5: Determinant as signed sum of clow sequence
  6. Lecture 6: Determinant has small ABP and Strassen's homogenization
  7. Lecture 7 : Depth reduction for arithmetic formulas
  8. Lecture 8 : Depth reduction for arithmetic circuits
  9. Lecture 9: Depth 4 reduction
  10. Lecture 10: Depth 3 reduction
  11. Lecture 11: Equivalence of Formulas and Width 3 ABP
  12. Lecture 12: Width-2 ABP Chasm
  13. Lecture 13: Grigoriev-Karpinski Measure
  14. Lecture 14: Lower Bound of Depth-3 circuit over finite fields
  15. Lecture 15: Lower Bound for depth 3 Multilinear Circuits
  16. Lecture 16: Lower Bound for Constant depth Multilinear Circuits
  17. Lecture 17: Structural lemma for constant depth multilinear circuits
  18. Lecture 18: Extending the proof for multilinear formulas
  19. Lecture 19: Shifted Partial Derivative Measure
  20. Lecture 20: Exponential Lower Bound for General depth-4 CIrcuits
  21. Lecture 21: Lower Bound on Homogeneous Depth-4 circuits
  22. Lecture 22: Introduction to PIT
  23. Lecture 23: Hitting Set and Hitting Set Generator
  24. Lecture 24: PIT vs Lower Bounds

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kanpur.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights