NPTEL : NOC:Arithmetic Circuit Complexity (Computer Science and Engineering)

Co-ordinators : Prof. Nitin Saxena


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