Undergraduate Complexity Theory
Rigorous introduction to computability and complexity theory, covering Turing machines, diagonalization, NP-completeness, space complexity, Savitch's theorem, and the polynomial hierarchy.
Ryan O'Donnell
Professor of Computer Science
Courses by Ryan O'Donnell
Complete university lecture series taught by Ryan O'Donnell.
Graduate Computational Complexity Theory
Intensive PhD-level complexity theory sequence examining circuit complexity, randomized computation, interactive proofs, PCP theorem foundations, pseudorandomness, and hardness amplification.
Analysis of Boolean Functions
Research-level course developing Fourier analysis over the Boolean hypercube, hypercontractivity, noise stability, invariance principles, and applications to hardness of approximation and social choice.
Quantum Computation and Quantum Information
Mathematical development of quantum circuits, entanglement, quantum query complexity, phase estimation, Shor's factoring algorithm, quantum channels, and quantum error correction.
A Theorist's Toolkit
Essential mathematical machinery for theoretical computer science research: asymptotic tail bounds, spectral graph theory, expanders, linear and semidefinite programming duality, and Fourier analysis.
Standalone talks by Ryan O'Donnell
10Self-contained public lectures, keynote addresses, and research seminars.
The Exponential Time Hypothesis: Foundations of Computational Hardness
An foundational lecture introducing the Exponential Time Hypothesis (ETH), a crucial conjecture in theoretical computer science that posits limits on efficient solvability for NP-hard problems.
Essential Hardness: Completing the Exponential Time Hypothesis Proof
This lecture, part of a graduate computational complexity course, delves into the intricate details required to complete the proof of the Exponential Time Hypothesis (ETH).
Quantum Factoring Algorithm: Finishing Rotation Estimation
Concluding the detailed exposition of the efficient quantum factoring algorithm, this lecture focuses on the final intricacies of rotation estimation in superposition.
Quantum Algorithms Recap: Hadamard Transform
Recapping the foundational role of the Hadamard Transform in quantum algorithms, this lecture provides a rigorous examination of its implications for quantum computation.
Rotation Estimation in Superposition: Part 1
An initial exploration into the dynamics of Rotation Estimation when applied to quantum superposition states, a critical component of advanced quantum algorithms.
Quantum Algorithms Recap: Grover's Algorithm and SAT
A focused review of quantum algorithms, specifically delving into Grover's Algorithm for the Boolean satisfiability problem, as part of a comprehensive quantum computing series.
Study paths featuring Ryan O'Donnell
1
6 steps · 8h
Boolean Fourier Analysis to Quantum Complexity
Harmonic analysis on the hypercube, linearity testing, social choice, and quantum circuits
Carnegie Mellon University
6 curated lecturesOpen path →
All lectures by Ryan O'Donnell
100Search or browse every recorded session across courses and talks.
Showing 20 of 100 lectures
Lecturej/k navigate · c chapters · s save · x watched
Scholar · University
Chapters · Duration
1:19:45
1:22:00
20:32
29:57
15:07
16:57
15-750 · Lec 3 · Ryan O'Donnell · Carnegie Mellon University
28:10
15-750 · Lec 4 · Ryan O'Donnell · Carnegie Mellon University
22:18
15-750 · Lec 5 · Ryan O'Donnell · Carnegie Mellon University
25:00
15-750 · Lec 7 · Ryan O'Donnell · Carnegie Mellon University
18:09
15-750 · Lec 2 · Ryan O'Donnell · Carnegie Mellon University
26:10
15-750 · Lec 1 · Ryan O'Donnell · Carnegie Mellon University
35:51
15-455 · Lec 5 · Ryan O'Donnell · Carnegie Mellon University
1:20:50
15-455 · Lec 17 · Ryan O'Donnell · Carnegie Mellon University
1:21:12
15-455 · Lec 20 · Ryan O'Donnell · Carnegie Mellon University
1:21:05
15-859 · Lec 4 · Ryan O'Donnell · Carnegie Mellon University
1:21:16
15-859 · Lec 18 · Ryan O'Donnell · Carnegie Mellon University
1:17:32
15-859 · Lec 1 · Ryan O'Donnell · Carnegie Mellon University
1:11:25
15-455 · Lec 2 · Ryan O'Donnell · Carnegie Mellon University
1:19:47
15-455 · Lec 14 · Ryan O'Donnell · Carnegie Mellon University
1:22:37