Media Storage Type : 32 GB USB Stick
NPTEL Subject Matter Expert : Prof. Nitin Saxena
NPTEL Co-ordinating Institute : IIT Kanpur
NPTEL Lecture Count : 26
NPTEL Course Size : 5.4 GB
NPTEL PDF Text Transcription : Available and Included
NPTEL Subtitle Transcription : Available and Included (SRT)
Lecture Titles:
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