Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Nitin Saxena
NPTEL Co-ordinating Institute : IIT Kanpur
NPTEL Lecture Count : 24
NPTEL Course Size : 21 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
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