Uploaded May 2020 | Updated November 2026, 3 hours ago
How fully-explicit expander graphs can be used to 'magically' decrease the error of a randomized algorithm while not increasing the number of random bits used (or hardly increasing it) . Lecture 16c 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:
"Expander graphs and their applications", by Hoory, Linial, and Wigderson.
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/)
How fully-explicit expander graphs can be used to 'magically' decrease the error of a randomized algorithm while not increasing the number of random bits used (or hardly increasing it) . Lecture 16c 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:
"Expander graphs and their applications", by Hoory, Linial, and Wigderson.
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)







