Completed
Course Introduction and Overview: Graduate Complexity Lecture 1 at CMU
Class Central Classrooms beta
YouTube videos curated by Class Central.
Classroom Contents
Graduate Complexity Theory
Automatically move to the next video in the Classroom when playback concludes
- 1 Course Introduction and Overview: Graduate Complexity Lecture 1 at CMU
- 2 Hierarchy Theorems (Time, Space, and Nondeterministic): Graduate Complexity Lecture 2 at CMU
- 3 Hopcroft--Paul--Valiant Theorem: Graduate Complexity Lecture 3 at CMU
- 4 Circuits: Graduate Complexity Lecture 4 at CMU
- 5 Probabilistic Complexity Classes: Graduate Complexity Lecture 5 at CMU
- 6 Quasilinear Cook--Levin Theorem: Graduate Complexity Lecture 6 at CMU
- 7 The Polynomial Time Hierarchy: Graduate Complexity Lecture 7 at CMU
- 8 Oracles, and the Polynomial Time Hierarchy vs. circuits: Graduate Complexity Lecture 8 at CMU
- 9 Improving Kannan's Theorem: Graduate Complexity Lecture 8 bonus material at CMU
- 10 Time/Space Tradeoffs for SAT: Graduate Complexity Lecture 9 at CMU
- 11 Introduction to Arthur-Merlin classes, MA and AM: Graduate Complexity Lecture 10 at CMU
- 12 More on constant-round interactive proof systems: Graduate Complexity Lecture 12 at CMU
- 13 Approximate counting: Graduate Complexity Lecture 12 at CMU
- 14 Valiant--Vazirani Theorem, and Exact Counting (#P): Graduate Complexity Lecture 13 at CMU
- 15 Toda's 1st Theorem and the Permanent: Graduate Complexity Lecture 14 at CMU
- 16 Permanent is #P-complete: Graduate Complexity Lecture 20 (out of order) at CMU
- 17 Algebraic Circuit Complexity: Graduate Complexity Lecture 15 at CMU
- 18 Algebraic "NP vs. P" vs. "Boolean NP vs. P": Graduate Complexity Lecture 15 postscript at CMU
- 19 Instance Checking and the Permanent: Graduate Complexity Lecture 16 at CMU
- 20 IP = PSPACE: Graduate Complexity Lecture 17 at CMU
- 21 Random Restrictions and AC0 Circuit Lower Bounds: Graduate Complexity Lecture 18 at CMU
- 22 The Switching Lemma: PRST version: Graduate Complexity Lecture 19 at CMU
- 23 Monotone circuit lower bounds: Graduate Complexity Lecture 21 at CMU
- 24 Razborov--Smolensky lower bounds for AC0[p]: Graduate Complexity Lecture 22 at CMU
- 25 Toda's 2nd Theorem and lower bounds for uniform ACC: Graduate Complexity Lecture 23 at CMU
- 26 Hardness vs. Randomness I: Graduate Complexity Lecture 24 at CMU
- 27 Hardness vs. Randomness II: Graduate Complexity Lecture 25 at CMU
- 28 Hardness amplification: Graduate Complexity Lecture 26 at CMU
- 29 Ironic complexity: Graduate Complexity Lecture 27 at CMU
