Ryan O'Donnell Courses

Constraint Satisfaction Problems - Lecture 20b of CS Theory Toolkit

1 rating

Explores constraint satisfaction problems through classic examples, approximation algorithms, and the P-versus-NP-complete dichotomy.

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

Why Study Quantum Computing? - Lesson 100 of Quantum Computer Programming in 100 Easy Lessons

Explore the significance and potential of quantum computing in this thought-provoking conclusion to a comprehensive series on quantum programming.

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

Quantum Algorithms Recap: Factoring - Lesson 99

Explore quantum algorithms for factoring and rotation estimation, understanding their efficiency in quantum computing.

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

Quantum Algorithms Recap: Grover's Algorithm and SAT - Lesson 98

Recap geometric and rotational aspects of quantum computing, focusing on Grover's Algorithm for SAT in this advanced quantum programming lesson.

• YouTube
• 17 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

Majorization theorems for Young diagrams produced by the RSK process connect random-word combinatorics with quantum-state estimation.

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

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

A research talk on constructing high-dimensional expanders from Chevalley groups using spectral expansion and coset complexes.

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

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

Explore one-qubit quantum computing through polarization, measurement, and the Elitzur–Vaidman bomb-detection algorithm.

• YouTube
• 1 hour 8 minutes
• Self-Paced
• Free Video

Improved Quantum Data Analysis - Shadow Tomography

A paper-driven talk on improving sample complexity for adaptive quantum shadow tomography and its connection to adaptive data analysis.

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

Deterministic Communication Complexity - Lecture 23b of CS Theory Toolkit

Learn formal deterministic communication protocols, communication matrices, combinatorial rectangles, equality complexity, and the Log Rank conjecture.

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

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

Explore why constraint satisfaction and related problems become tractable on trees and series-parallel graphs, using treewidth and dynamic programming.

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

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

Goemans–Williamson rounding turns Max-Cut SDP vectors into a randomized cut with a 0.878 approximation guarantee.

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

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

Learn how semidefinite programming relaxes the Max-Cut problem into an efficiently solvable infinite linear program.

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