Learn · Computational Complexity Theory

Lecture 16 of 41week 5

Lecture 16: Bounded Depth Circuit Classes

Prof. Raghunath Tewari · IIT Kanpur

Credits and licence

From
Computational Complexity Theory, 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: Introduction Video
  2. Lecture 2: NP Completeness Video
  3. Lecture 3: SAT is NP-complete Video
  4. Lecture 4: More on NP completeness Video
  5. Lecture 05: Hierarchy Theorems Video
  6. Lecture 06: Introduction to Space Complexity Video
  7. Lecture 07: Savitch's Theorem Video
  8. Lecture 08: Immerman-Szelepscenyi Theorem Video
  9. Lecture 09: Polynomial Hierarchy Video
  10. Lecture 10: A PSPACE Complete Problem Video
  11. Lecture 11: More on Polynomial Hierarchy Video
  12. Lecture 12: Alternating Turing Machines Video
  13. Lecture 13: Equivalence of Quantifier and Oracle Based Definitions of Polynomial Hierarchy Video
  14. Lecture 14: Boolean Circuits Video
  15. Lecture 15: Shannon's Theorem and Karp-Lipton-Sipser Theorem Video
  16. Lecture 16: Bounded Depth Circuit Classes Video
  17. Lecture 17: Kannan's Theorem Video
  18. Lecture 18: Probabilistic Complexity Video
  19. Lecture 19: StrongBPP and WeakBPP Video
  20. Lecture 20: One-sided and Zero-sided Error Probabilistic Complexity Classes Video
  21. Lecture 21: Error Reduction for BPP Video
  22. Lecture 22: BPP in PH and Logspace Randomized Classes Video
  23. Lecture 23: Valiant-Vazirani Theorem - I Video
  24. Lecture 24: Valiant-Vazirani Theorem - I Video
  25. Lecture 25: Amplified version of Valiant-Vazirani Theorem Video
  26. Lecture 26: Toda's Theorem - I Video
  27. Lecture 27: Toda's Theorem - II Video
  28. Lecture 28: Permanent and Determinant Functions Video
  29. Lecture 29: Permanent is hard for #P Video
  30. Lecture 30: Interactive Proofs Video
  31. Lecture 31: Graph Non-Isomorphism is in IP[2] Video
  32. Lecture 32: Set Lower Bound Protocol Video
  33. Lecture 33: MA is in AM Video
  34. Lecture 34: Sumcheck Protocol - I Video
  35. Lecture 35: Sumcheck Protocol - II Video
  36. Lecture 36: Parity not in AC0 - I Video
  37. Lecture 37: Parity not in AC0 - II Video
  38. Lecture 38 : Circuits with Counters Video
  39. Lecture 39 : Communication Complexity - I Video
  40. Lecture 40 : PCP Theorem Video
  41. Lecture 41 : Communication Complexity - II Video