# Arithmetic Circuit Complexity

- Institution: IIT Kanpur
- Department: Computer Science and Engineering
- Teacher: Prof. Nitin Saxena
- Level: Undergraduate
- Language: English
- Subjects: Computer science, Engineering
- Source: [NPTEL](https://nptel.ac.in/courses/106104221)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106104221)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

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 independence, etc. The related tools are FFT (fast fourier transform), tensor rank, Newton's identity, ABP (algebraic branching program), PIT (polynomial identity testing), Wronskian, Jacobian, etc. One surprising result here is that certain problems for general circuits reduce to depth-3 circuits. Furthermore, the algorithmic question of PIT is related to proving circuit lower bounds.We then move on to proofs, or attempts to prove, that certain problems are hard and impossible to express as a small circuit (i.e. hard to solve in real life too). One such problem is Permanent. We study the hardness against restricted models-- diagonal circuits, homogeneous depth-3, homogeneous depth-4, noncommutative formulas, multilinear depth-3, multilinear formulas, read-once ABP, etc. The partial derivatives, and the related spaces, of a circuit will be a key tool in these proofs. The holy grail here is the VP/VNP question.Depending on time and interest, other advanced topics could be included. One such growing area is-- GCT (geometric complexity theory) approach to the P/NP question.

INTENDED AUDIENCE : Intersted students PREREQUISITES : Preferable (but not necessary)-- Theory of Computation, Algorithms, Algebra INDUSTRY SUPPORT : Cryptography, Coding theory, Symbolic Computing Software, Learning Software

## Lectures

1. [Lecture 1: Turing Machines and Introduction to Arithmetic Circuits](https://invisiblenetwork.ai/learn/nptel/106104221/95d085864ce1) (YouTube)
2. [Lecture 2: Arithmetic complexity classes](https://invisiblenetwork.ai/learn/nptel/106104221/831f9bba5bf0) (YouTube)
3. [Lecture 3: Determinant is in VP](https://invisiblenetwork.ai/learn/nptel/106104221/15372125ef59) (YouTube)
4. [Lecture 4: Determinant vs Arithmetic Branching Programs (ABP)](https://invisiblenetwork.ai/learn/nptel/106104221/edd0df930a29) (YouTube)
5. [Lecture 5: Determinant as signed sum of clow sequence](https://invisiblenetwork.ai/learn/nptel/106104221/c71959a57052) (YouTube)
6. [Lecture 6: Determinant has small ABP and Strassen's homogenization](https://invisiblenetwork.ai/learn/nptel/106104221/3d5b8e1e8586) (YouTube)
7. [Lecture 7 : Depth reduction for arithmetic formulas](https://invisiblenetwork.ai/learn/nptel/106104221/2cbe0c2a832f) (YouTube)
8. [Lecture 8 : Depth reduction for arithmetic circuits](https://invisiblenetwork.ai/learn/nptel/106104221/c3d049fd4b7b) (YouTube)
9. [Lecture 9: Depth 4 reduction](https://invisiblenetwork.ai/learn/nptel/106104221/d5b9bcd464f7) (YouTube)
10. [Lecture 10: Depth 3 reduction](https://invisiblenetwork.ai/learn/nptel/106104221/432b4f47b4b8) (YouTube)
11. [Lecture 11: Equivalence of Formulas and Width 3 ABP](https://invisiblenetwork.ai/learn/nptel/106104221/c3d8e5d2716a) (YouTube)
12. [Lecture 12: Width-2 ABP Chasm](https://invisiblenetwork.ai/learn/nptel/106104221/c4058bd564ac) (YouTube)
13. [Lecture 13: Grigoriev-Karpinski Measure](https://invisiblenetwork.ai/learn/nptel/106104221/f65805c1ac38) (YouTube)
14. [Lecture 14: Lower Bound of Depth-3 circuit over finite fields](https://invisiblenetwork.ai/learn/nptel/106104221/56d4f693aca4) (YouTube)
15. [Lecture 15: Lower Bound for depth 3 Multilinear Circuits](https://invisiblenetwork.ai/learn/nptel/106104221/3ca49175e443) (YouTube)
16. [Lecture 16: Lower Bound for Constant depth Multilinear Circuits](https://invisiblenetwork.ai/learn/nptel/106104221/012d38f5725b) (YouTube)
17. [Lecture 17: Structural lemma for constant depth multilinear circuits](https://invisiblenetwork.ai/learn/nptel/106104221/d83dff376778) (YouTube)
18. [Lecture 18: Extending the proof for multilinear formulas](https://invisiblenetwork.ai/learn/nptel/106104221/38aeff91b3ce) (YouTube)
19. [Lecture 19: Shifted Partial Derivative Measure](https://invisiblenetwork.ai/learn/nptel/106104221/c1b1f27f02ff) (YouTube)
20. [Lecture 20: Exponential Lower Bound for General depth-4 CIrcuits](https://invisiblenetwork.ai/learn/nptel/106104221/889e7878cc4d) (YouTube)
21. [Lecture 21: Lower Bound on Homogeneous Depth-4 circuits](https://invisiblenetwork.ai/learn/nptel/106104221/affda8247832) (YouTube)
22. [Lecture 22: Introduction to PIT](https://invisiblenetwork.ai/learn/nptel/106104221/01170f55a75a) (YouTube)
23. [Lecture 23: Hitting Set and Hitting Set Generator](https://invisiblenetwork.ai/learn/nptel/106104221/190cc94cd2e9) (YouTube)
24. [Lecture 24: PIT vs Lower Bounds](https://invisiblenetwork.ai/learn/nptel/106104221/194eec1ba48c) (YouTube)