Spectral Graph Theory: conductance and Sparsest-Cut || @ CMU || Lecture 15b of CS Theory Toolkit @RyanODonnellTeaching
Spectral Graph Theory: conductance and Sparsest-Cut || @ CMU || Lecture 15b of CS Theory Toolkit  @RyanODonnellTeaching
Uploaded May 2020 | Updated November 2026, 6 hours ago
Spectral Graph Theory III: The conductance of vertex sets, the minimum conductance in a graph, the Sparsest-Cut problem, and Cheeger's inequality stated. Lecture 15b of "CS Theory Toolkit": a semester-long graduate course on math and CS fundamentals for research in theoretical computer science, taught at Carnegie Mellon University.

Resource for this lecture:
"Spectral and Algebraic Graph Theory" book by Spielman

Taught by Ryan O'Donnell (https://www.cs.cmu.edu/~odonnell)

Course homepage on CMU's Diderot system: https://www.diderot.one/course/28/

Filmed by Cole H. for Panopto (panopto.com/)

Thumbnail photo by Rebecca Kiger (rebeccakphoto.com/)
Spectral Graph Theory: conductance and Sparsest-Cut || @ CMU || Lecture 15b of CS Theory Toolkit#88/100: Planes of rotation for IncrL, Part 1|| Quantum Computer Programming in 100 Easy Lessons#58/100: Tiny angle errors are not a problem || Quantum Computer Programming in 100 Easy LessonsSpectral Graph Theory: the Laplacian, and the Spectral Theorem || @ CMU || 14b of CS Theory ToolkitError Correcting Codes problems || @ CMU || Recitation 7 of CS Theory Toolkit#3/100: What you will dislike about this course || Quantum Computer Programming in 100 Easy Lessons#13/100: Composite quantum instructions || Quantum Computer Programming in 100 Easy Lessons#69/100: The order of measuring doesnt matter || Quantum Computer Programming in 100 Easy Lessons#83/100: The Hadamard Test: analysis || Quantum Computer Programming in 100 Easy LessonsLearning About Quantum States 1:  Intro to Quantum ComputationSpectral Graph Theory: The Quadratic Form || @ CMU || Lecture 13a of CS Theory ToolkitThe SYK Model: Classical and Quantum Algorithms
Ryan ODonnell |

Spectral Graph Theory: conductance and Sparsest-Cut || @ CMU || Lecture 15b of CS Theory Toolkit

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER