Learn · Arithmetic Circuit Complexity
Lecture 15 of 24Week 8: Lower Bounds on Multilinear Circuits
Lecture 15: Lower Bound for depth 3 Multilinear Circuits
Prof. Nitin Saxena · IIT Kanpur
Credits and licence
- From
- Arithmetic Circuit Complexity, IIT Kanpur (at NPTEL)
- Licence
- CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
- Attribution
- NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
- Who can watch
- Tweens profiles and older. How courses are placed
All the 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