# Circuit Complexity Theory

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

## Lectures

1. [Lecture 01: Introduction I](https://invisiblenetwork.ai/learn/nptel/106104241/817eb2d13c83) (Video)
2. [Lecture 02: Introduction II](https://invisiblenetwork.ai/learn/nptel/106104241/43e7bfdefdb7) (Video)
3. [Lecture 03: Lower bound for circuits](https://invisiblenetwork.ai/learn/nptel/106104241/1738e0b95923) (Video)
4. [Lecture 04: Lower bound for formulas](https://invisiblenetwork.ai/learn/nptel/106104241/7e8c903af251) (Video)
5. [Lecture 05: Khrapchenko's theorem](https://invisiblenetwork.ai/learn/nptel/106104241/01b06707b8dd) (Video)
6. [Lecture 06: Proof of Khrapchenko's Theorem](https://invisiblenetwork.ai/learn/nptel/106104241/8ca5a99783a8) (Video)
7. [Lecture 07: Applications of Khrapchenko's Theorem](https://invisiblenetwork.ai/learn/nptel/106104241/301eed084368) (Video)
8. [Lecture 08: Nechiporuk's Theorem](https://invisiblenetwork.ai/learn/nptel/106104241/7c17e709d3bd) (Video)
9. [Lecture 09: Applications of Nechiporuk's Theorem](https://invisiblenetwork.ai/learn/nptel/106104241/7a338932da64) (Video)
10. [Lecture 10: Subbotovskaya's Theorem I](https://invisiblenetwork.ai/learn/nptel/106104241/bbae4b468d76) (Video)
11. [Lecture 11: Subbotovskaya's Theorem II](https://invisiblenetwork.ai/learn/nptel/106104241/219e14d67517) (Video)
12. [Lecture 12: Applications of Subbotovskaya's Theorem](https://invisiblenetwork.ai/learn/nptel/106104241/1fd1f3d48a0e) (Video)
13. [Lecture 13: Upper and Lower Bounds on the Andreev Function](https://invisiblenetwork.ai/learn/nptel/106104241/343e5eb7878b) (Video)
14. [Lecture 14: Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/90873389ffd8) (Video)
15. [Lecture 15: Polynomial Size Monotone Formula for MAJORITY (Valiant's Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/aae73b397768) (Video)
16. [Lecture 16: Circuits for Addition Ripple Adder and Carry Lookahead Adder](https://invisiblenetwork.ai/learn/nptel/106104241/b1718efcf612) (Video)
17. [Lecture 17: Circuits for Addition Parallel Prefix Sum Method](https://invisiblenetwork.ai/learn/nptel/106104241/9dc288ea1272) (Video)
18. [Lecture 18: Circuits for Iterated Addition and Multiplication](https://invisiblenetwork.ai/learn/nptel/106104241/a73a93f9fdc4) (Video)
19. [Lecture 19: Bounded Depth Circuit Classes](https://invisiblenetwork.ai/learn/nptel/106104241/830141b8de96) (Video)
20. [Lecture 20: Basic Circuit for Division using NewtonRaphson Method](https://invisiblenetwork.ai/learn/nptel/106104241/07e1d5359097) (Video)
21. [Lecture 21: Division in NC1 (Beame, Cook, Hoover Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/ee5a73f98e9a) (Video)
22. [Lecture 22: Division in NC1 (Beame, Cook, Hoover Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/7ede896473c2) (Video)
23. [Lecture 23: Division in NC1 (Beame, Cook, Hoover Theorem) III](https://invisiblenetwork.ai/learn/nptel/106104241/07065e8c4668) (Video)
24. [Lecture 24: Division in NC1 (Beame, Cook, Hoover Theorem) IV](https://invisiblenetwork.ai/learn/nptel/106104241/b7500ed0e951) (Video)
25. [Lecture 25: Division in NC1 (Beame, Cook, Hoover Theorem) V](https://invisiblenetwork.ai/learn/nptel/106104241/1e673fa6c812) (Video)
26. [Lecture 26: Division in NC1 (Beame, Cook, Hoover Theorem) VI](https://invisiblenetwork.ai/learn/nptel/106104241/7077343678d9) (Video)
27. [Lecture 27: Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes I](https://invisiblenetwork.ai/learn/nptel/106104241/2e226fbb66db) (Video)
28. [Lecture 28: Relation between Bounded Depth Circuit Classes and Uniform Complexity Classes II](https://invisiblenetwork.ai/learn/nptel/106104241/bb46fddd4812) (Video)
29. [Lecture 29: Reducing Circuit Depth](https://invisiblenetwork.ai/learn/nptel/106104241/496b723e4686) (Video)
30. [Lecture 30: P is in P/poly](https://invisiblenetwork.ai/learn/nptel/106104241/1d85347c9042) (Video)
31. [Lecture 31: Discussion on Circuit Lower Bounds for Bounded Depth Circuit Classes](https://invisiblenetwork.ai/learn/nptel/106104241/9c79558e69b1) (Video)
32. [Lecture 32: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/d0e7ed996c60) (Video)
33. [Lecture 33: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/ef44274dedba) (Video)
34. [Lecture 34: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) III](https://invisiblenetwork.ai/learn/nptel/106104241/e2bfddd2a138) (Video)
35. [Lecture 35: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) IV](https://invisiblenetwork.ai/learn/nptel/106104241/cc1424aec6b5) (Video)
36. [Lecture 36: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) V](https://invisiblenetwork.ai/learn/nptel/106104241/0a16574a79b5) (Video)
37. [Lecture 37: Monotone Circuit Lower Bound for Clique (Razborov's Theorem) VI](https://invisiblenetwork.ai/learn/nptel/106104241/43f76ca14ee7) (Video)
38. [Lecture 38: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/77fa5a2fbb28) (Video)
39. [Lecture 39: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/810ae58d1175) (Video)
40. [Lecture 40: Circuit Lower Bound for Parity by Approximating Circuits using Polynomials (RazborovSmolensky Theorem) III](https://invisiblenetwork.ai/learn/nptel/106104241/31bd72b0e36e) (Video)
41. [Lecture 41: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/03e5ee7d0bcb) (Video)
42. [Lecture 42: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/e35148a3661a) (Video)
43. [Lecture 43: Circuit Lower Bound for Parity using Switching Lemma (Hastad's Theorem) III](https://invisiblenetwork.ai/learn/nptel/106104241/5f1808f94366) (Video)
44. [Lecture 44: Proof of Hastad's Switching Lemma I](https://invisiblenetwork.ai/learn/nptel/106104241/14c1e28a7448) (Video)
45. [Lecture 45: Proof of Hastad's Switching Lemma II](https://invisiblenetwork.ai/learn/nptel/106104241/a7c1b908ee52) (Video)
46. [Lecture 46: Communication Complexity of a Function](https://invisiblenetwork.ai/learn/nptel/106104241/a65eb14df033) (Video)
47. [Lecture 47: Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/c163e8e8bb8c) (Video)
48. [Lecture 48: Relation Between Communication Complexity and Circuit Depth (KarchmerWigderson Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/eafb81867b83) (Video)
49. [Lecture 49: Bounded Width Branching Programs = NC1 (Barrington's Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/9fe381ead5d9) (Video)
50. [Lecture 50: Bounded Width Branching Programs = NC1 (Barrington's Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/9e997f5753d3) (Video)
51. [Lecture 51: Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/e5c6a6312d88) (Video)
52. [Lecture 52: Width 3 Branching Programs = MOD3 o MOD2 circuits (Barrington's Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/4ec41f024fcd) (Video)
53. [Lecture 53: Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/04a65ae4f9c1) (Video)
54. [Lecture 54: Uniform AC0 can be simulated by depth 3 Threshold circuits of quasipolynomial size (AllenderHertramph Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/c88492680116) (Video)
55. [Lecture 55: ValiantVazirani Theorem I](https://invisiblenetwork.ai/learn/nptel/106104241/9e7b698a90fe) (Video)
56. [Lecture 56: ValiantVazirani Theorem II](https://invisiblenetwork.ai/learn/nptel/106104241/8f626010b5aa) (Video)
57. [Lecture 57: Natural Proof Barrier (RazborovRudich Theorem) I](https://invisiblenetwork.ai/learn/nptel/106104241/278050516257) (Video)
58. [Lecture 58: Natural Proof Barrier (RazborovRudich Theorem) II](https://invisiblenetwork.ai/learn/nptel/106104241/32869bbaa88a) (Video)
59. [Lecture 59: Pseudorandom Function Generator by Goldreich, Goldwasser and Micali I](https://invisiblenetwork.ai/learn/nptel/106104241/3fd3e47ae901) (Video)
60. [Lecture 60: Pseudorandom Function Generator by Goldreich, Goldwasser and Micali II](https://invisiblenetwork.ai/learn/nptel/106104241/0587238ce166) (Video)