NOC:Randomized Methods in Complexity

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

Lecture 18 - Hardness vs Randomness

Lecture 19 - 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

Lecture 25 - Introduction to List Decoding

Lecture 26 - Local List decoding of WH, RM