Ryan O'Donnell Courses

Constraint Satisfaction Problems - Lecture 20b of CS Theory Toolkit

1 rating

Explore Constraint Satisfaction Problems, their formal definition, examples, and algorithms. Learn about the Dichotomy Theorem and its implications for theoretical computer science research.

• YouTube
• 32 minutes
• Self-Paced
• Free Video

Great Ideas in Theoretical Computer Science

Explore fundamental concepts in theoretical computer science including logic, computability, complexity theory, algorithms, probability, and quantum computing through CMU lectures.

• YouTube
• 1 day 8 hours 35 minutes
• Self-Paced
• Free Video

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
• Self-Paced
• Free Video

Analysis of Boolean Functions

Dive into Fourier analysis, noise stability, social choice theory, and computational complexity through 23 graduate-level lectures covering Boolean function analysis fundamentals.

• YouTube
• 1 day 5 hours 49 minutes
• Self-Paced
• Free Video

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
• Self-Paced
• Free Video

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
• Self-Paced
• Free Video

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
• Self-Paced
• Free Video

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
• Self-Paced
• Free Video

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
• Self-Paced
• Free Video

Dinur's PCP- Degree-Reduction, Expanderizing, Mini-PCP - Lecture 27c of CS Theory Toolkit

Explore Dinur's PCP Theorem proof, covering degree-reduction, expanderizing, and alphabet-reduction in theoretical computer science. Gain insights into advanced concepts for research in computational complexity.

• YouTube
• 26 minutes
• Self-Paced
• Free Video

Deterministic Communication Complexity - Lecture 23b of CS Theory Toolkit

Explore deterministic communication complexity, protocols, matrices, and the Log Rank conjecture in this graduate-level lecture on theoretical computer science fundamentals.

• YouTube
• 37 minutes
• Self-Paced
• Free Video

Trees and Series-Parallel Graphs - Lecture 22a of CS Theory Toolkit

Explore treewidth, CSPs, and graph theory fundamentals for theoretical computer science research, focusing on trees and series-parallel graphs.

• YouTube
• 21 minutes
• Self-Paced
• Free Video

Goemans-Williamson: Rounding the Max-Cut SDP - Lecture 20a of CS Theory Toolkit

Efficient algorithm for approximating maximum graph cuts using semidefinite programming and randomized rounding, with guaranteed performance ratio of 0.878.

• YouTube
• 32 minutes
• Self-Paced
• Free Video

The SDP Relaxation for Max-Cut - Lecture 19b of CS Theory Toolkit

Explore SDP relaxation for Max-Cut, transforming a quadratic program into a semidefinite program solvable by the Ellipsoid Algorithm. Part of CMU's graduate-level CS Theory Toolkit course.

• YouTube
• 33 minutes
• Self-Paced
• Free Video

The Ellipsoid Algorithm - Lecture 19a of CS Theory Toolkit

Explore the Ellipsoid Algorithm for solving Linear Programming and convex optimization, focusing on its polynomial-time efficiency and use of separation oracles in theoretical computer science.

• YouTube
• 31 minutes
• Self-Paced
• Free Video