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/)
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/)








![From One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit
Definitions of cryptographic pseudorandom generators (PRGs), one-way functions (OWFs), and related concepts. The famous [HILL] Theorem proving that PRGs and hence symmetric key encryption (SKE) can be constructed from (weak) OWFs is mentioned, as are Impagliazzos Five Worlds. Lecture 25c 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:
A course in cryptography by Pass and Shelat.
Taught by Ryan ODonnell (https://www.cs.cmu.edu/~odonnell)
Course homepage on CMUs Diderot system: https://www.diderot.one/course/28/
Thumbnail photo by Rebecca Kiger (https://www.rebeccakphoto.com/) From One-Way Functions to Symmetric Key Encryption || @ CMU || Lecture 25c of CS Theory Toolkit](https://i.ytimg.com/vi/c4SrYqN6ItY/mqdefault.jpg)

