Ryan O'Donnell Courses

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

Linear Programming - Bit Complexity - Lecture 17c of CS Theory Toolkit

Explore bit complexity in Linear Programming, feasible solutions, and the implications for NP ∩ coNP. Delve into fundamental concepts for theoretical computer science research.

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

Linear Programming Duality - Lecture 17b of CS Theory Toolkit

Explore linear programming duality, Farkas Lemma, and Fourier-Motzkin elimination in this graduate-level lecture on fundamental concepts for theoretical computer science research.

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

Expander Graph Application 2: Derandomization - Lecture 16c of CS Theory Toolkit

Explore derandomization techniques using expander graphs to reduce error in randomized algorithms without significantly increasing random bits used.

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

Expander Graph Constructions - Lecture of CS Theory Toolkit

Explore explicit expander graph constructions, including Gabber-Galil, Ramanujan, and Zig-Zag product expanders. Learn about their properties, applications, and mathematical foundations in theoretical computer science.

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

Spectral Graph Theory - Eigenvalues at CMU - Lecture 15a of CS Theory Toolkit

Explore eigenvalues of the Laplacian and Markov operator in spectral graph theory, including associated formulas and their applications in theoretical computer science research.

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

Spectral Graph Theory - Minimizing/Maximizing the Quadratic Form

Explore spectral graph theory, focusing on minimizing and maximizing quadratic forms, with connections to graph components and bipartiteness in this graduate-level lecture.

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

Spectral Graph Theory - The Quadratic Form

Explores spectral graph theory, focusing on the quadratic form associated with undirected graphs. Covers basic setup and provides examples for graduate-level computer science research.

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

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

Explore Hamming and Hadamard codes: linear error correction techniques with contrasting rate and distance properties. Learn their applications in theoretical computer science research.

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

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

Explore linear error correcting codes, their properties, and applications in computer science theory. Learn about decoding, notation, and minimum distance in this graduate-level lecture.

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

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

Explore fundamental axioms of quantum mechanics for quantum computing, covering unitary matrices, qubit gates, and quantum circuits in this graduate-level lecture from Carnegie Mellon University.

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

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

Explore Fourier analysis of Boolean functions, focusing on real-valued functions and their Fourier transforms in this graduate-level theoretical computer science lecture.

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

Fast Fourier Transform - Lecture 7c of CS Theory Toolkit

Explore the Fast Fourier Transform algorithm and its application in efficient integer multiplication, with insights from a CMU graduate-level computer science theory course.

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

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

Explore the Word RAM model for algorithms and its impact on integer sorting complexity in this graduate-level lecture on theoretical computer science fundamentals.

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

Computational Models - Turing Machines - CMU - CS Theory Toolkit

Explore Turing Machines as a computational model, covering historical advantages, multitape variations, and key concepts like memory, time, and space bounds in theoretical computer science.

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