NOC:Arithmetic Circuit Complexity


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