Computational Complexity Theory Courses and Certifications

Ryan O'Donnell

Undergraduate Computational Complexity Theory

Explore fundamental computational complexity theory through 28 comprehensive lectures covering P vs NP, reductions, space complexity, and randomized algorithms from Carnegie Mellon.

• YouTube
• 1 day 13 hours 36 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Graduate Complexity Theory

Dive into advanced computational complexity theory with graduate-level lectures covering hierarchy theorems, circuits, interactive proofs, and cutting-edge research topics.

• YouTube
• 1 day 11 hours 50 minutes
• On-Demand
• Free Video

Ryan O'Donnell

The Switching Lemma - PRST Version - Graduate Complexity Lecture at CMU

Explore the Switching Lemma in computational complexity theory, focusing on the PRST version and its proof, with insights on decision trees and probability bounds.

• YouTube
• 55 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Time-Space Tradeoffs for SAT - Graduate Complexity Lecture at CMU

Explore time/space tradeoffs for SAT in this graduate-level complexity theory lecture, covering key results, proofs, and techniques like padding and alternation elimination.

• YouTube
• 1 hour 32 minutes
• On-Demand
• Free Video

Ryan O'Donnell

The Polynomial Time Hierarchy: Graduate Complexity Lecture at CMU

Explore the Polynomial Time Hierarchy in computational complexity theory, covering definitions, examples, and key concepts like quantifying over circuits and alternation.

• YouTube
• 1 hour 19 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Hierarchy Theorems - Time, Space, and Nondeterministic: Graduate Complexity Lecture at CMU

Explore hierarchy theorems in computational complexity, covering time, space, and nondeterministic aspects. Gain insights into encoding schemes, Turing machines, and nondeterministic certificates.

• YouTube
• 1 hour 21 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Hopcroft-Paul-Valiant Theorem - Graduate Complexity Lecture at CMU

Explore the Hopcroft-Paul-Valiant theorem in computational complexity, covering simulation, graph analysis, and pebble games. Gain insights into low space simulation and depth reduction techniques.

• YouTube
• 1 hour 20 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Circuits - Graduate Complexity Lecture 4 at CMU

Explore graduate-level computational complexity theory, focusing on circuits, complexity measures, and lower bounds in this advanced lecture from Carnegie Mellon University.

• YouTube
• 1 hour 20 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - Why is P vs. NP Difficult?

Explore the challenges of the P vs. NP problem in computational complexity theory, including negative results, Ladner's theorem, and simulations.

• YouTube
• 1 hour 20 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - Oracle Turing Machines and P^NP

Explore oracle Turing machines and P^NP in computational complexity theory, focusing on solving algorithms, consequences, and the Minimum Circuit Problem.

• YouTube
• 1 hour 22 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - BPP

Explore probabilistic algorithms and complexity class BPP in this advanced lecture on computational theory, featuring axis property amplification and upper bounds.

• YouTube
• 1 hour 20 minutes
• On-Demand
• Free Video

Ryan O'Donnell

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

Explore randomized complexity classes RP, coRP, and ZPP, covering probabilistic Turing machines, error amplification, and nondeterminism in computational complexity theory.

• YouTube
• 1 hour 22 minutes
• On-Demand
• Free Video

Ryan O'Donnell

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

Explore the Immerman--Szelepcsényi Theorem in computational complexity theory, covering key concepts, proofs, and implications for nondeterministic space complexity classes.

• YouTube
• 1 hour 21 minutes
• On-Demand
• Free Video

Ryan O'Donnell

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

Explore P-completeness, reductions, and PSPACE-completeness in computational complexity theory, covering key concepts like the Cook-Levin Theorem and TQBF.

• YouTube
• 1 hour 20 minutes
• On-Demand
• Free Video

Ryan O'Donnell

Undergrad Complexity at CMU - Savitch's Theorem and NL

Explore Savitch's Theorem and NL in computational complexity theory, focusing on space complexity, recursion, and pseudocode implementation for advanced undergraduate-level understanding.

• YouTube
• 1 hour 21 minutes
• On-Demand
• Free Video