Completed
Ironic complexity: Graduate Complexity Lecture 27 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
