Complexity Theory Courses and Certifications

Ryan O'Donnell

Undergrad Complexity at CMU - Randomized Complexity- RP, coRP, and ZPP

Explores randomized computation through probabilistic Turing machines and the complexity classes RP, coRP, and ZPP, including one-sided error and error amplification.

• YouTube
• 1 hour 22 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - The Immerman-Szelepcsényi Theorem

Explore the Immerman–Szelepcsényi theorem and its surprising proof that nondeterministic log-space is closed under complement.

• YouTube
• 1 hour 21 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - From P-Completeness to PSPACE-Completeness

Explores P-completeness and PSPACE-completeness through log-space reductions, circuit evaluation, Cook–Levin, and quantified Boolean formulas.

• YouTube
• 1 hour 20 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - Savitch's Theorem and NL

Explores Savitch's Theorem and nondeterministic log space by relating space-bounded computation to reachability in implicitly defined configuration graphs.

• YouTube
• 1 hour 21 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - NP

Explore NP through polynomial-time verification, satisfiability, and the question of whether finding solutions is as easy as checking them.

• YouTube
• 1 hour 21 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - SAT

Explore SAT across Boolean circuits, formulas, CNF, k-SAT, and 3-SAT, including NP-completeness and a polynomial-time algorithm for 2-SAT.

• YouTube
• 1 hour 20 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - Problems in P

Examines P through concrete graph and sequence problems, comparing brute-force running times with polynomial-time algorithms.

• YouTube
• 1 hour 22 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - Turing Machines

Formalize algorithms with Turing machines, from tape-based computation and machine definitions to deciders that solve languages and decision problems.

• YouTube
• 1 hour 20 minutes
• Self-Paced
• Free Video

GKR Protocol and IP=PSPACE - Lecture 3

Delve into advanced cryptography concepts focusing on IP=PSPACE applications and the GKR Protocol through detailed mathematical proofs and theoretical frameworks.

• YouTube
• 1 hour 22 minutes
• Self-Paced
• Free Video

Probabilistically Checkable Proofs via GKR and Interactive Arguments - Lecture 4

Delve into probabilistically checkable proofs (PCP), exploring their construction through GKR protocol and interactive succinct arguments for NP in advanced cryptography.

• YouTube
• 1 hour 30 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Razborov-Smolensky Lower Bounds for AC0[p] - Graduate Complexity Lecture at CMU

Proves Razborov–Smolensky lower bounds showing that constant-depth circuits with MOD p gates require exponential size for parity.

• YouTube
• 1 hour 13 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Permanent is #P-Complete: Graduate Complexity Lecture at CMU

Graduate proof that computing the permanent of a 0–1 matrix is #P-complete, using reductions from #3SAT and cycle-cover gadgets.

• YouTube
• 1 hour 14 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Algebraic Circuit Complexity

A graduate lecture on algebraic complexity theory, using arithmetic circuits to study polynomial computation, division elimination, and the permanent–determinant problem.

• YouTube
• 1 hour 20 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

Approximate Counting - Graduate Complexity Lecture at CMU

Explore how approximate counting connects randomized computation, decision problems, and interactive proofs in graduate computational complexity theory.

• YouTube
• 1 hour 20 minutes
• Self-Paced
• Free Video

Ryan O'Donnell

More on Constant-Round Interactive Proof Systems - Graduate Complexity Lecture at CMU

Graduate lecture on constant-round interactive proofs, Merlin–Arthur classes, public and private coins, and complexity-theoretic applications including graph isomorphism.

• YouTube
• 1 hour 21 minutes
• Self-Paced
• Free Video