# Randomized Methods in 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/106104228)
- Licence: [CC BY-NC-SA](https://nptel.ac.in/faq) (Non-commercial use only.)
- Syllabus: [at the source](https://nptel.ac.in/courses/106104228)
- Who can watch: Tweens profiles and older (sources give no ratings; placed by Invisible Network from the source's own words)

## Lectures

1. [Lecture 1: Course Outline](https://invisiblenetwork.ai/learn/nptel/106104228/746950672f4f) (Video)
2. [Lecture 2 Circuits and Polynomial Identity Testing](https://invisiblenetwork.ai/learn/nptel/106104228/839f429dbf48) (Video)
3. [Lecture 3: Derandomization and Lower Bounds](https://invisiblenetwork.ai/learn/nptel/106104228/e14f83112061) (Video)
4. [Lecture 4: IP=PSPACE](https://invisiblenetwork.ai/learn/nptel/106104228/96261ae32d0a) (Video)
5. [Lecture 5: ACC0 Lower Bounds](https://invisiblenetwork.ai/learn/nptel/106104228/b3d0b8d8bc07) (Video)
6. [Lecture 6: ACC0 Lower Bounds Continued.](https://invisiblenetwork.ai/learn/nptel/106104228/266889ecdbdc) (Video)
7. [Lecture 7: Monotone Circuits](https://invisiblenetwork.ai/learn/nptel/106104228/126c28ac8b34) (Video)
8. [Lecture 8: Monotone Circuit Lower Bound and Sunflower Lemma.](https://invisiblenetwork.ai/learn/nptel/106104228/0ccdbfb1654d) (Video)
9. [Lecture 9: Undirected Graph Connectivity in randomized logspace.](https://invisiblenetwork.ai/learn/nptel/106104228/e48edbd7dc57) (Video)
10. [Lecture 10: Graph Expansion Properties.](https://invisiblenetwork.ai/learn/nptel/106104228/fb4dbd768a20) (Video)
11. [Lecture 11: Expanders](https://invisiblenetwork.ai/learn/nptel/106104228/6a2f9093eb64) (Video)
12. [Lecture 12: Error Reduction using Expanders](https://invisiblenetwork.ai/learn/nptel/106104228/904b347993c1) (Video)
13. [Lecture 13: Ajtai-Komlos-Szemeredi Theorem](https://invisiblenetwork.ai/learn/nptel/106104228/bc5fa21dea03) (Video)
14. [Lecture 14: Explicit construction of expanders and Zig-Zag product](https://invisiblenetwork.ai/learn/nptel/106104228/72021f412a95) (Video)
15. [Lecture 15: Spectral analysis of Zig-Zag product](https://invisiblenetwork.ai/learn/nptel/106104228/9b5b8f11b675) (Video)
16. [Lecture 16: Undirected Path in logspace](https://invisiblenetwork.ai/learn/nptel/106104228/46a739e70957) (Video)
17. [Lecture 17: Explicit Prg to derandomizing classes](https://invisiblenetwork.ai/learn/nptel/106104228/2a494ce78eca) (Video)
18. [Hardness vs Randomness.](https://invisiblenetwork.ai/learn/nptel/106104228/c077cff90493) (Video)
19. [Hardness to NW-Generator to PRG](https://invisiblenetwork.ai/learn/nptel/106104228/b20027c5dae5) (Video)
20. [Lecture 20: Partial derandomization from worst-case hardness of permanent](https://invisiblenetwork.ai/learn/nptel/106104228/164a528f3843) (Video)
21. [Lecture 21: Error-correcting codes](https://invisiblenetwork.ai/learn/nptel/106104228/556f67bdc98d) (Video)
22. [Lecture 22: Introduction to various linear explicit codes](https://invisiblenetwork.ai/learn/nptel/106104228/27aaf9b2712b) (Video)
23. [Lecture 23: Introduction of efficient decoding](https://invisiblenetwork.ai/learn/nptel/106104228/5e087c35a90a) (Video)
24. [Lecture 24: Local decoding of WH, Reed-Muller and Concatenated codes](https://invisiblenetwork.ai/learn/nptel/106104228/8ba7c7455d83) (Video)
25. [Week 25: Introduction to List Decoding](https://invisiblenetwork.ai/learn/nptel/106104228/bb1aef3dd713) (Video)
26. [Lecture 26: Local List decoding of WH, RM](https://invisiblenetwork.ai/learn/nptel/106104228/c129e9968a4e) (Video)