Ryan O'Donnell Courses

Undergrad Complexity at CMU - Hardness within P

Explore computational complexity theory, focusing on hardness within P, time hierarchy theorem, and fine-grained complexity. Delve into reductions, algorithms, and open questions in this advanced undergraduate lecture.

• YouTube
• 1 hour 22 minutes
• On-Demand
• Free Online Course

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 Online Course

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 Online Course

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 Online Course

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 Online Course

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 Online Course

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 Online Course

Undergrad Complexity at CMU - NP

Explore NP complexity, verification, and key features in computational theory. Delve into stronger conjectures, brute force algorithms, and proofs for squares and colors.

• YouTube
• 1 hour 21 minutes
• On-Demand
• Free Online Course

Undergrad Complexity at CMU - SAT

Explore the intricacies of SAT in computational complexity theory, covering Boolean circuits, algorithms, and CNF formulas in this comprehensive undergraduate lecture.

• YouTube
• 1 hour 20 minutes
• On-Demand
• Free Online Course

Undergrad Complexity at CMU - Problems in P

Explore computational complexity theory, focusing on problems in P, simulations, and Turing machine variants. Learn about time hierarchy, natural problems, and efficient algorithms.

• YouTube
• 1 hour 22 minutes
• On-Demand
• Free Online Course

Undergrad Complexity at CMU - Turing Machines

Explore Turing Machines in computational complexity theory, covering formalization, the Turing Thesis, examples, and mathematical definitions for a comprehensive understanding.

• YouTube
• 1 hour 20 minutes
• On-Demand
• Free Online Course

Learning About Quantum States - Majorization Theorems for the RSK Process

Explore combinatorial theorems on RSK process applied to random words, focusing on Young diagram majorization in different scenarios.

• YouTube
• 22 minutes
• On-Demand
• Free Online Course

High-Dimensional Expanders - How I Learned to Stop Worrying and Love Group-Theoretic Constructions

Explore high-dimensional expanders, focusing on 2-dimensional cases, graphs of constant link, and group-theoretic constructions. Gain insights into advanced mathematical concepts and recent research developments.

• YouTube
• 47 minutes
• On-Demand
• Free Online Course

Quantum Computing with Just 1 Qubit - The Elitzur-Vaidman Bomb Algorithm

Explore quantum computing fundamentals and the Elitzur-Vaidman bomb detection algorithm using a single qubit, covering key concepts and practical applications in this engaging lecture.

• YouTube
• 1 hour 8 minutes
• On-Demand
• Free Online Course

Improved Quantum Data Analysis - Shadow Tomography

Explore improved quantum shadow tomography, focusing on optimal dependence on observables, dimension, and error tolerance. Learn connections to adaptive data analysis in this advanced talk.

• YouTube
• 59 minutes
• On-Demand
• Free Online Course