Ryan O'Donnell
Professor · Carnegie Mellon University · author of Analysis of Boolean Functions
Ryan O'Donnell is a Carnegie Mellon computer science professor known for the analysis of Boolean functions and quantum computation.
- lectures
- 199
- series
- 6
- hours
- 173
Start here
Series and courses
CMU 15-859BB: Quantum Computation and Quantum Information
Open the course
- 1 Parallel Universes
- 2Rotate, Compute, Rotate
- 3Understanding and Measuring One Qubit
- 4Unitary Transformations and the Elitzur–Vaidman Bomb
Show 23 moreShow fewer
- 5Discriminating Two Qubits
- 6Multi-Qubit Systems
- 7Multiplying By A Global Phase Doesn't Make A Difference
- 8Partial Measurements and Spooky Action at a Distance
- 9The CHSH Game
- 10No Cloning Theorem, and Quantum Teleportation
- 11Quantum Money
- 12Basics of Quantum Computing
- 13Revealing XOR-patterns I
- 14Revealing XOR-patterns II
- 15Simon's Algorithm
- 16The Fourier Transform over
- 17Period-Finding (Simon's Algorithm over )
- 18Shor's Factoring Algorithm
- 19The Hidden Subgroup Problem
- 20Grover's Algorithm
- 21Quantum Query Complexity
- 22The Adversary Method in Quantum Query Complexity
- 23Mixed States and Density Matrices
- 24Quantum Probability
- 25Quantum Information Theory
- 26Quantum Complexity
- 27Quantum "Supremacy"
CMU 15-455: Undergraduate Complexity Theory
Open the course
- 1Course Overview and Formal Definition of Computation
- 2Turing Machines
- 3Simulations and Turing Machine Variants
- 4Time Complexity and Universal Turing Machines
Show 20 moreShow fewer
- 5Time Hierarchy Theorem
- 6Problems in P
- 7Boolean Satisfiability (SAT)
- 8The Complexity Class NP
- 9Nondeterminism
- 10Reductions
- 13Search-to-Decision, Padding, Dichotomy Theorems
- 14Ladner's Theorem and Mahaney's Theorem
- 15The Complexity Class coNP
- 16Space Complexity
- 17Savitch's Theorem and NL
- 18NL-Completeness and Logspace Reductions
- 19From P-Completeness to PSPACE-Completeness
- 20The Immerman-Szelepcsényi Theorem
- 21Randomized Complexity: RP, coRP, and ZPP
- 24Oracle Turing Machines and
- 25Interactive Proofs: IP=PSPACE
- 26Beyond Worst-Case Analysis
- 27Hardness within P
- 28Why is P vs. NP Difficult?
CMU 15-859: Analysis of Boolean Functions
Open the course
- 1The Fourier Expansion and Basic Formulas
- 2Probability Densities and BLR Linearity Testing
- 3Social Choice and Influences
- 4Noise Stability and Arrow's Theorem
Show 18 moreShow fewer
- 5Spectral Concentration and Learning
- 6Restrictions and the Goldreich-Levin Theorem
- 7DNF Formulas
- 8Linial-Mansour-Nisan Theorems
- 9Majority, LTFs, and the CLT
- 10LTFs and Noise Stability
- 11Level-1 Inequality and the 2/π Theorem
- 12Bonami's Lemma and the KKL Theorem
- 13Dictator Testing and the FKN Theorem
- 14Probabilistically Checkable Proofs of Proximity
- 15Constraint Satisfaction Problems
- 16Håstad's Hardness Theorems
- 18The Hypercontractivity Theorem
- 19Invariance Theorems
- 20Majority Is Stablest Theorem
- 21Analysis of Boolean Functions: Additive Combinatorics
- 22Sanders's Theorem (Analysis of Boolean Functions, CMU 15-859S, Lecture 22)
- 23Analysis of Boolean Functions: Open Problems
CMU 15-855: Graduate Computational Complexity Theory
Open the course
- 1Course Introduction and Overview
- 2Hierarchy Theorems (Time, Space, and Nondeterministic)
- 3Hopcroft–Paul–Valiant Theorem
- 4Circuits
Show 23 moreShow fewer
- 5Probabilistic Complexity Classes
- 6Quasilinear Cook–Levin Theorem
- 7The Polynomial Time Hierarchy
- 8Oracles, and the Polynomial Time Hierarchy vs. circuits
- 9Time/Space Tradeoffs for SAT
- 10Introduction to Arthur-Merlin classes, MA and AM
- 11More on constant-round interactive proof systems
- 12Approximate counting
- 13Valiant–Vazirani Theorem, and Exact Counting (#P)
- 14Toda's 1st Theorem and the Permanent
- 15Algebraic Circuit Complexity
- 16Instance Checking and the Permanent
- 17IP = PSPACE
- 18Permanent is #P-complete
- 19Random Restrictions and AC0 Circuit Lower Bounds
- 20The Switching Lemma: PRST Version
- 21Monotone Circuit Lower Bounds
- 22Razborov Smolensky Lower Bounds for AC0[p]
- 23Toda's Second Theorem and Lower Bounds for Uniform ACC
- 24Hardness vs. Randomness I
- 25Hardness vs. Randomness II
- 26Hardness Amplification
- 27Ironic Complexity
Quantum Computer Programming in 100 Easy Lessons
CMU 15-750: A Theorist's Toolkit
Open the course
Show 85 moreShow fewer
- 5Asymptotics Tricks
- 6Birthday Paradox Asymptotics
- 7Factorial Asymptotics, Stirling's Formula
- 8Binomial Coefficients Asymptotics
- 9Central Limit Theorem
- 10Gaussian Random Variables
- 11Berry–Esseen Theorem
- 12Markov and Chebyshev Inequalities
- 13Proof of the Chernoff Bound
- 14Chernoff, Hoeffding, etc. bounds
- 15Computational Models: Turing Machines
- 16Computational Models: Circuits
- 17The Word RAM Model
- 18Complexity of Basic Arithmetic
- 19Multiplication via the Discrete Fourier Transform
- 20Fast Fourier Transform (FFT) and Integer Multiplication
- 21Fourier Analysis of Boolean Functions
- 22Boolean Fourier Formulas
- 23Analysis of Boolean Functions: Applications in Social Choice
- 24Quantum Computing Overview
- 25Axioms of Quantum Computing
- 26Grover's Algorithm
- 27Primes and Prime Fields
- 28Non-Prime Fields
- 29Communication Complexity of Equality
- 30Multivariate Polynomials and the Schwartz Zippel Lemma
- 31Error Correcting Codes
- 32Linear Error Correcting Codes
- 33Hamming Code and Hadamard Code
- 34Reed Solomon Codes
- 35Pseudorandom Generators
- 36Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators
- 37k-wise Independent Generators
- 38Epsilon-Biased Generators
- 39Spectral Graph Theory: The Quadratic Form
- 40Spectral Graph Theory: The Standard Random Walk
- 41Spectral Graph Theory: Linear Algebra and Irregular Graphs
- 42Spectral Graph Theory: Minimizing and Maximizing the Quadratic Form
- 43Spectral Graph Theory: The Markov Transition Operator
- 44Spectral Graph Theory: The Laplacian and the Spectral Theorem
- 45Spectral Graph Theory III: Eigenvalues of the Laplacian
- 46Spectral Graph Theory: Conductance and Sparsest-Cut
- 47Spectral Graph Theory III: Mixing Time
- 48Cheeger's Inequality
- 49Expander Graphs Overview
- 50Expander Graphs Application 1: Good Codes
- 51Expander Graph Application 2: Derandomization
- 52Expander Graph Constructions
- 53Linear Programming Duality
- 54Linear Programming: Bit Complexity
- 55Linear Programming: Optimization Reduces to Feasibility
- 56Max-st-Flow is a Linear Program
- 57Relaxing Integer Linear Programs to Linear Programs: Bipartite Maximum Perfect Matching
- 58Rounding LP Solutions: Minimum Vertex Cover
- 59Min-st-Cut is the Dual LP of Max-st-Flow
- 60The Ellipsoid Algorithm
- 61The Semidefinite Programming Relaxation for Max-Cut
- 62Solving the Max-Cut SDP
- 63Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
- 64Constraint Satisfaction Problems
- 65CSP Approximability: Optimization and Certification
- 66Proof Complexity for CSPs: Sherali-Adams and Sum-of-Squares Proof Systems
- 67The Sherali-Adams Proof System
- 68The Sum-of-Squares (SOS) Proof System
- 69Pseudoexpectations
- 70Trees and Series-Parallel Graphs
- 71Treewidth Definitions
- 72Algorithms for Bounded Treewidth
- 73Basics of Communication Complexity
- 74Deterministic Communication Complexity
- 75Yao's Minimax Theorem and 's Communication Complexity
- 76Entropy
- 77Mutual Information
- 78Information Complexity
- 79Introduction to Cryptography: Symmetric Key Encryption and the One-Time Pad
- 80Computational Indistinguishability
- 81From One-Way Functions to Symmetric Key Encryption
- 82Learning With Errors (LWE) and Public Key Encryption
- 83Hardness of Random 3XOR and 3Sat
- 84Exponential Time Hypotheses: ETH and SETH
- 85NP-Hardness of Approximation
- 86Statement of the PCP Theorem
- 87Dinur's Proof of the PCP Theorem: Outline
- 88Dinur's PCP Theorem: Degree-Reduction, Expanderizing, and Mini-PCP
- 89Dinur's Proof of the PCP Theorem: The Powering Step
In these lectures
Draws on
People cited in the lectures, at the moment of the citation.
- Peter ShorPublished a polynomial-time algorithm for factoring on a quantum computer in 1994.
- Claude Shannon1949 paper showing every function on n bits has a circuit of size order .
- Ryan WilliamsMIT computer science researcher whose PhD thesis work on SAT lower bounds is cited.
- Johan HåstadCited for his work on hardness of approximation and dictatorship tests.
- Manuel BlumFaculty member at the university.
- László BabaiPublished a 2016 paper giving a quasi-polynomial time algorithm for Graph Isomorphism.
Playlists
4About
Ryan O'Donnell is a Carnegie Mellon computer science professor known for the analysis of Boolean functions and quantum computation. O'Donnell's courses span undergraduate complexity theory to graduate quantum computation, proving IP = PSPACE, Valiant's theorem and the Chernoff bound.
Taught with
Same subject, Algorithms & Theoretical CS
Connections
213Their places, courses, books and lectures.
Courses6
Lectures199
- Harmonic Numbers Asymptotics
- The Fourier Expansion and Basic Formulas
- The Complexity Class coNP
- Asymptotics Tricks
- The Word RAM Model
- The CHSH Game
Show 193 moreShow fewer
- Understanding and Measuring One Qubit
- Central Limit Theorem
- IP = PSPACE
- Binomial Coefficients Asymptotics
- Birthday Paradox Asymptotics
- Approximate counting
- Factorial Asymptotics, Stirling's Formula
- Street Fighting Mathematics
- Proof of the Chernoff Bound
- The Immerman-Szelepcsényi Theorem
- Revealing XOR-patterns II
- Permanent is #P-complete
- Probability Densities and BLR Linearity Testing
- No Cloning Theorem, and Quantum Teleportation
- Unitary Transformations and the Elitzur–Vaidman Bomb
- $10^{500}$ Parallel Universes
- Course Overview and Formal Definition of Computation
- Majority, LTFs, and the CLT
- The Hypercontractivity Theorem
- Håstad's Hardness Theorems
- Expander Graphs Application 1: Good Codes
- The Fourier Transform over $\mathbb{Z}_n$
- Communication Complexity of Equality
- Social Choice and Influences
- Multi-Qubit Systems
- Analysis of Boolean Functions: Open Problems
- Time/Space Tradeoffs for SAT
- Quantum Money
- Linial-Mansour-Nisan Theorems
- Level-1 Inequality and the 2/π Theorem
- Markov and Chebyshev Inequalities
- The Sherali-Adams Proof System
- The Complexity Class NP
- Spectral Graph Theory: The Quadratic Form
- Invariance Theorems
- Simon's Algorithm
- Mixed States and Density Matrices
- Space Complexity
- Simulations and Turing Machine Variants
- Dictator Testing and the FKN Theorem
- Berry–Esseen Theorem
- Spectral Graph Theory: Minimizing and Maximizing the Quadratic Form
- Random Restrictions and AC0 Circuit Lower Bounds
- Reductions
- Computational Models: Circuits
- Fourier Analysis of Boolean Functions
- Goemans-Williamson Algorithm: Rounding the Max-Cut SDP
- Boolean Fourier Formulas
- Constraint Satisfaction Problems
- Bonami's Lemma and the KKL Theorem
- Probabilistic Complexity Classes
- Noise Stability and Arrow's Theorem
- Hardness within P
- Turing Machines
- Instance Checking and the Permanent
- Grover's Algorithm
- Exponential Time Hypotheses: ETH and SETH
- Search-to-Decision, Padding, Dichotomy Theorems
- Hopcroft–Paul–Valiant Theorem
- Toda's 1st Theorem and the Permanent
- Randomized Complexity: RP, coRP, and ZPP
- Gaussian Random Variables
- Deterministic Communication Complexity
- Revealing XOR-patterns I
- Expander Graph Application 2: Derandomization
- Rotate, Compute, Rotate
- Shor's Factoring Algorithm
- Savitch's Theorem and NL
- The Hidden Subgroup Problem
- Epsilon-Biased Generators
- Period-Finding (Simon's Algorithm over $\mathbb{Z}_N$)
- Boolean Satisfiability (SAT)
- Restrictions and the Goldreich-Levin Theorem
- Rounding LP Solutions: Minimum Vertex Cover
- Hierarchy Theorems (Time, Space, and Nondeterministic)
- Time Complexity and Universal Turing Machines
- Nondeterminism
- Big O and friends
- NL-Completeness and Logspace Reductions
- Relaxing Integer Linear Programs to Linear Programs: Bipartite Maximum Perfect Matching
- Computational Models: Turing Machines
- Pseudorandom Generators
- LTFs and Noise Stability
- Spectral Concentration and Learning
- Computational Indistinguishability
- Proof Complexity for CSPs: Sherali-Adams and Sum-of-Squares Proof Systems
- Circuits
- How to do CS Theory
- Partial Measurements and Spooky Action at a Distance
- The Switching Lemma: PRST Version
- The Adversary Method in Quantum Query Complexity
- Ladner's Theorem and Mahaney's Theorem
- Introduction to Cryptography: Symmetric Key Encryption and the One-Time Pad
- Axioms of Quantum Computing
- Course Introduction and Overview
- Spectral Graph Theory: Linear Algebra and Irregular Graphs
- Constraint Satisfaction Problems
- Valiant–Vazirani Theorem, and Exact Counting (#P)
- From P-Completeness to PSPACE-Completeness
- Time Hierarchy Theorem
- CSP Approximability: Optimization and Certification
- Quantum Algorithms Synthesis I: The Hadamard Transform
- Entropy
- Spectral Graph Theory: The Standard Random Walk
- DNF Formulas
- Algebraic Circuit Complexity
- Cheeger's Inequality
- Quantum Phase & Rotation Estimation in Superposition
- Completing Shor's Quantum Period-Finding & Factoring Algorithm
- Problems in P
- Razborov Smolensky Lower Bounds for AC0[p]
- From One-Way Functions to Symmetric Key Encryption
- Spectral Graph Theory III: Eigenvalues of the Laplacian
- Oracles, and the Polynomial Time Hierarchy vs. circuits
- Basics of Quantum Computing
- Sanders's Theorem (Analysis of Boolean Functions, CMU 15-859S, Lecture 22)
- Probabilistically Checkable Proofs of Proximity
- Ironic Complexity
- Spectral Graph Theory: The Markov Transition Operator
- Spectral Graph Theory: Conductance and Sparsest-Cut
- The Polynomial Time Hierarchy
- Dinur's Proof of the PCP Theorem: Outline
- Max-st-Flow is a Linear Program
- Analysis of Boolean Functions: Additive Combinatorics
- Majority Is Stablest Theorem
- Interactive Proofs: IP=PSPACE
- Chernoff, Hoeffding, etc. bounds
- Fast Fourier Transform (FFT) and Integer Multiplication
- Introduction to Arthur-Merlin classes, MA and AM
- Quantum Probability
- Primes and Prime Fields
- Hamming Code and Hadamard Code
- Yao's Minimax Theorem and $\mathrm{IP}_2$'s Communication Complexity
- Multivariate Polynomials and the Schwartz Zippel Lemma
- Orthogonal Rotation Planes of Controlled-Increment Gates
- Complexity of Basic Arithmetic
- Hardness Amplification
- Reed Solomon Codes
- Linear Programming Duality
- Discriminating Two Qubits
- Treewidth Definitions
- Multiplication via the Discrete Fourier Transform
- More on constant-round interactive proof systems
- Error Correcting Codes
- The Ellipsoid Algorithm
- Hardness of Random 3XOR and 3Sat
- Hardness vs. Randomness I
- Information Complexity
- Mutual Information
- Quantum Query Complexity
- Impagliazzo T Wigderson, and Nisan's Pseudorandom Generators
- Linear Error Correcting Codes
- Quantum Algorithms Synthesis II: Grover's Search & Circuit SAT
- Hardness vs. Randomness II
- Spectral Graph Theory III: Mixing Time
- Dinur's Proof of the PCP Theorem: The Powering Step
- Expander Graphs Overview
- Spectral Graph Theory: The Laplacian and the Spectral Theorem
- Quantum "Supremacy"
- Algorithms for Bounded Treewidth
- The Sum-of-Squares (SOS) Proof System
- k-wise Independent Generators
- Non-Prime Fields
- Linear Programming: Optimization Reduces to Feasibility
- Learning With Errors (LWE) and Public Key Encryption
- Grover's Algorithm
- NP-Hardness of Approximation
- Toda's Second Theorem and Lower Bounds for Uniform ACC
- Oracle Turing Machines and $P^{\mathrm{NP}}$
- Quasilinear Cook–Levin Theorem
- Why is P vs. NP Difficult?
- Solving the Max-Cut SDP
- Expander Graph Constructions
- Linear Programming: Bit Complexity
- Quantum Complexity
- Trees and Series-Parallel Graphs
- The Exponential Time Hypothesis: Foundations of Computational Hardness
- The Semidefinite Programming Relaxation for Max-Cut
- Constructing Uniform Superpositions of Quantum Phase States
- Quantum Information Theory
- Min-st-Cut is the Dual LP of Max-st-Flow
- Monotone Circuit Lower Bounds
- Basics of Communication Complexity
- Statement of the PCP Theorem
- Pseudoexpectations
- Beyond Worst-Case Analysis
- Quantum Algorithms Synthesis III: Efficient Factoring & BQP
- Analysis of Boolean Functions: Applications in Social Choice
- The Existence of a Non-Sofic Group
- Multiplying By A Global Phase Doesn't Make A Difference
- Essential Hardness: Completing the Exponential Time Hypothesis Proof
- Quantum Computing Overview
- Dinur's PCP Theorem: Degree-Reduction, Expanderizing, and Mini-PCP










