Learn · NPTEL

Course10610422826 lectures

Randomized Methods in Complexity

Prof. Nitin Saxena · IIT Kanpur

Start with lecture 1 At NPTEL

Lectures

Week 1

  1. Lecture 1: Course Outline Video
  2. Lecture 2 Circuits and Polynomial Identity Testing Video

Week 2

  1. Lecture 3: Derandomization and Lower Bounds Video
  2. Lecture 4: IP=PSPACE Video

Week 3

  1. Lecture 5: ACC0 Lower Bounds Video
  2. Lecture 6: ACC0 Lower Bounds Continued. Video

Week 4

  1. Lecture 7: Monotone Circuits Video
  2. Lecture 8: Monotone Circuit Lower Bound and Sunflower Lemma. Video

Week 5

  1. Lecture 9: Undirected Graph Connectivity in randomized logspace. Video
  2. Lecture 10: Graph Expansion Properties. Video
  3. Lecture 11: Expanders Video

Week 6

  1. Lecture 12: Error Reduction using Expanders Video
  2. Lecture 13: Ajtai-Komlos-Szemeredi Theorem Video

Week 7

  1. Lecture 14: Explicit construction of expanders and Zig-Zag product Video
  2. Lecture 15: Spectral analysis of Zig-Zag product Video

Week 8

  1. Lecture 16: Undirected Path in logspace Video
  2. Lecture 17: Explicit Prg to derandomizing classes Video

Week 9

  1. Hardness vs Randomness. Video
  2. Hardness to NW-Generator to PRG Video

Week 10

  1. Lecture 20: Partial derandomization from worst-case hardness of permanent Video
  2. Lecture 21: Error-correcting codes Video

Week 11

  1. Lecture 22: Introduction to various linear explicit codes Video
  2. Lecture 23: Introduction of efficient decoding Video

Week 12

  1. Lecture 24: Local decoding of WH, Reed-Muller and Concatenated codes Video
  2. Week 25: Introduction to List Decoding Video
  3. Lecture 26: Local List decoding of WH, RM Video

Syllabus and materials

At NPTEL, as the course publishes them.

Credits and licence

Institution
IIT Kanpur
Department
Computer Science and Engineering
Teacher
Prof. Nitin Saxena
Level
Undergraduate
Language
English
Subjects
Computer science, Engineering
Source
NPTEL
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only. NPTEL's terms
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
NPTEL gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed