Learn · Randomized Methods in Complexity

Lecture 6 of 26Week 3

Lecture 6: ACC0 Lower Bounds Continued.

Prof. Nitin Saxena · IIT Kanpur

Credits and licence

From
Randomized Methods in Complexity, IIT Kanpur (at NPTEL)
Licence
CC BY-NC-SA, as NPTEL states it. Non-commercial use only.
Attribution
NPTEL states: "Distributed under Creative Commons Attribution-ShareAlike / CC BY - NC - SA", beside a BY-NC-SA badge.
Who can watch
Tweens profiles and older. How courses are placed

All the lectures

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