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