Uploaded June 2020 | Updated November 2026, 3 hours ago
Linear Programming duality, the Farkas Lemma, and Fourier-Motzkin elimination. Lecture 17b 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:
"Understanding and Using Linear Programming" by Matoušek and Gärtner
"Geometric Algorithms and Combinatorial Optimization" by Grötschel, Lovász, and Schrijver
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/)
Linear Programming duality, the Farkas Lemma, and Fourier-Motzkin elimination. Lecture 17b 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:
"Understanding and Using Linear Programming" by Matoušek and Gärtner
"Geometric Algorithms and Combinatorial Optimization" by Grötschel, Lovász, and Schrijver
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)



