The SDP Relaxation for Max-Cut || @ CMU || Lecture 19b of CS Theory Toolkit @RyanODonnellTeaching
The SDP Relaxation for Max-Cut || @ CMU || Lecture 19b of CS Theory Toolkit  @RyanODonnellTeaching
Uploaded June 2020 | Updated November 2026, 1 day ago
Taking an exact quadratic program for Max-Cut, relaxing it to a linear program with "infinitely many constraints", and recognizing this as a "semidefinite program" that can be efficiently solved with the Ellipsoid Algorithm. Lecture 19b 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.

Resources for this lecture:
"Geometric Algorithms and Combinatorial Optimization" by Grötschel, Lovász, and Schrijver.
"Laplacian eigenvalues and the maximum cut problem" by Delorme and Poljak.

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

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

Thumbnail photo by Rebecca Kiger (rebeccakphoto.com/)
The SDP Relaxation for Max-Cut || @ CMU || Lecture 19b of CS Theory Toolkit#84/100: Factoring Algorithm: the overview || Quantum Computer Programming in 100 Easy LessonsLinear Programming Duality || @ CMU || Lecture 17b of CS Theory ToolkitThe Switching Lemma#6/100: Creating and destroying qubits || Quantum Computer Programming in 100 Easy LessonsEntropy || @ CMU || Lecture 24a of CS Theory ToolkitExpander Graph Application 2: Derandomization || @ CMU || Lecture 16c of CS Theory ToolkitHardness Assumptions Beyond NP ≠ P || @ CMU || Lecture 26a of CS Theory ToolkitDinurs proof of the PCP Theorem: the Powering step || @ CMU || Lecture 27d of CS Theory ToolkitFrom One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit#44/100: Discriminating 2 qubits, no false poss || Quantum Computer Programming in 100 Easy LessonsDinurs Proof of the PCP Theorem: outline || @ CMU || Lecture 27b of CS Theory Toolkit
Ryan ODonnell |

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

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER