Ryan O'Donnell Courses

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 Video

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

Explore the #P-completeness of the Permanent problem in this advanced computational complexity theory lecture, covering key concepts and reduction techniques.

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

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

IP = PSPACE - Graduate Complexity Lecture at CMU

Explore interactive proof systems and their relationship to complexity classes, focusing on the IP = PSPACE theorem and its implications for computational theory.

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

Algebraic Circuit Complexity

Explore algebraic circuit complexity, including models, formulas, and NP connections in computational complexity theory.

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

Approximate Counting - Graduate Complexity Lecture at CMU

Explore advanced computational complexity theory, focusing on approximate counting techniques, Chebyshev's Inequality, and interactive proofs in this graduate-level lecture.

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

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

Explore constant-round interactive proof systems in computational complexity theory, covering MA, AM, BPP, and efficient error reduction techniques.

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

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

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

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

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

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

Hardness of Approximation - Part 1

Explore hardness of approximation in computational complexity, covering Max Cut, Independent Set, and K-Cover problems. Learn key definitions, algorithms, and current research state.

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

Ryan O'Donnell Tutorial on Hardness of Approximation - Part 3

Explore advanced concepts in approximation algorithms, focusing on Max 3-Lin, Fourier analysis, and edge weights in optimization problems.

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

Great Ideas in Theoretical Computer Science: Time Complexity - Spring 2016

Explore time complexity in theoretical computer science, covering running time, worst-case scenarios, and common runtime scaling, with practical examples and formal definitions.

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