Ryan O'Donnell Courses

Spectral Graph Theory - Minimizing/Maximizing the Quadratic Form

Analyze how graph quadratic forms are minimized and maximized, connecting their extremal values to connected components and bipartiteness.

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

Spectral Graph Theory - The Quadratic Form

Introduces the graph quadratic form as an edge-based measure of variation, connecting indicator functions to edge boundaries and cuts.

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

Hamming Code and Hadamard Code - Lecture 11c of CS Theory Toolkit

Explore Hamming and Hadamard codes, contrasting high-rate single-error correction with low-rate codes whose codewords are maximally separated.

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

Linear Error Correcting Codes - Lecture 11b of CS Theory Toolkit

Learn how linear error-correcting codes use generator and parity-check matrices to encode, decode, and analyze minimum distance.

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

Axioms of Quantum Computing - Lecture 9b of CS Theory Toolkit

Learn the axioms of quantum mechanics that underpin quantum computing, from qubit states and unitary gates to measurement and quantum circuits.

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

Fourier Analysis of Boolean Functions - Lecture 8a of CS Theory Toolkit

Introduces Fourier analysis of Boolean functions through Boolean-cube representations, multilinear polynomials, Fourier coefficients, and majority and parity examples.

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

Fast Fourier Transform - Lecture 7c of CS Theory Toolkit

Explains how the Fast Fourier Transform recursively multiplies a discrete Fourier transform matrix in O(n log n) time, enabling fast integer multiplication.

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

The Word RAM Model - Lecture 6c of CS Theory Toolkit

Explores the Word RAM model and the complexity of integer sorting, including radix sort and open questions in the transdichotomous model.

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

Computational Models - Turing Machines - CMU - CS Theory Toolkit

Examines Turing machines as computational models, comparing single-tape, multitape, and random-access designs through their time and space costs.

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

Factorial Asymptotics, Stirling's Formula - Lecture 3b of CS Theory Toolkit

Derive increasingly sharp asymptotic bounds for n!, culminating in Stirling’s formula with its √(2πn) constant and 1+O(1/n) refinement.

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

Big O and Friends - Lecture 2a of CS Theory Toolkit

A graduate-level lecture on Big O, little o, Omega notation, tilde notation, and standard function forms for comparing asymptotic growth.

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

Quantum "Supremacy" - Lecture 25 of Quantum Computation at CMU

Examine quantum supremacy through fault tolerance, random circuit sampling, and complexity-theoretic evidence for quantum advantage.

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

Quantum Complexity - Quantum Computation at CMU

Examines how quantum computation fits into complexity theory through BQP, factoring, NP, and related complexity classes.

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

Quantum Query Complexity - Quantum Computation at CMU

A lecture formalizing the quantum query model and comparing quantum, randomized, and deterministic query complexity through Simon’s, Grover’s, and related problems.

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

Shor's Factoring Algorithm - Lecture 16 of Quantum Computation at CMU

A number-theoretic walkthrough of Shor’s algorithm, using periodicity, modular exponentiation, fractions, and GCDs to recover factors.

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