IIT Kanpur · Computer Science

Randomized Methods in Complexity

Prof. Nitin Saxena · 26 free video lectures

26 video lectures. Topics: Course Outline; Circuits and Polynomial Identity Testing; Derandomization and Lower Bounds; IP=PSPACE; ACC0 Lower Bounds; ACC0 Lower Bounds Continued.; Monotone Circuits; Monotone Circuit Lower Bound and Sunflower Lemma.; Undirected Graph Connectivity in randomized…

▶ Play on Open Lecture HallCourse page ↗

Lectures

  1. Lecture 1: Course Outline
  2. Lecture 2 Circuits and Polynomial Identity Testing
  3. Lecture 3: Derandomization and Lower Bounds
  4. Lecture 4: IP=PSPACE
  5. Lecture 5: ACC0 Lower Bounds
  6. Lecture 6: ACC0 Lower Bounds Continued.
  7. Lecture 7: Monotone Circuits
  8. Lecture 8: Monotone Circuit Lower Bound and Sunflower Lemma.
  9. Lecture 9: Undirected Graph Connectivity in randomized logspace.
  10. Lecture 10: Graph Expansion Properties.
  11. Lecture 11: Expanders
  12. Lecture 12: Error Reduction using Expanders
  13. Lecture 13: Ajtai-Komlos-Szemeredi Theorem
  14. Lecture 14: Explicit construction of expanders and Zig-Zag product
  15. Lecture 15: Spectral analysis of Zig-Zag product
  16. Lecture 16: Undirected Path in logspace
  17. Lecture 17: Explicit Prg to derandomizing classes
  18. Hardness vs Randomness.
  19. Hardness to NW-Generator to PRG
  20. Lecture 20: Partial derandomization from worst-case hardness of permanent
  21. Lecture 21: Error-correcting codes
  22. Lecture 22: Introduction to various linear explicit codes
  23. Lecture 23: Introduction of efficient decoding
  24. Lecture 24: Local decoding of WH, Reed-Muller and Concatenated codes
  25. Week 25: Introduction to List Decoding
  26. Lecture 26: Local List decoding of WH, RM

From NPTEL (IITs and IISc) · CC BY-NC-SA. More from IIT Kanpur.

Open Lecture Hall is free, with no ads and no sign-up. It is not run by or connected to any university; the lectures are the universities' own free recordings, played from where they host them. About & rights