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