Expander Graph Constructions || @ CMU || Lecture 16d of CS Theory Toolkit @RyanODonnellTeaching
Expander Graph Constructions || @ CMU || Lecture 16d of CS Theory Toolkit  @RyanODonnellTeaching
Uploaded May 2020 | Updated November 2026, 1 day ago
An overview of some explicit expander graph constructions: The (Margulis-)Gabber-Galil expanders, the Margulis/Lubotzky--Phillips--Sarnak Ramanujan graph expanders, and the Reingold--Vadhan--Wigderson Zig-Zag product expanders. The "Replacement Product" variant of the Zig-Zag construction is sketched. Lecture 16d 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/)
Expander Graph Constructions || @ CMU || Lecture 16d of CS Theory Toolkit#71/100: Entanglement || Quantum Computer Programming in 100 Easy LessonsPanteleev Kalachev Codes:  Asymptotically good quantum LDPC codes and classical LTCsTreewidth Definitions || @ CMU || Lecture 22b of CS Theory ToolkitLearning About Quantum States 5:  The Robinson Schensted Knuth AlgorithmLearning About Quantum States 6: Central Limit Theorems and more for the RSK process on random wordsGreat Ideas in Theoretical Computer Science: Introduction (Spring 2016) reupload with improved audio#37/100: Rotations in 2-D || Quantum Computer Programming in 100 Easy Lessons#98/100: Quantum algs recap: Grovers Alg & SAT || Quantum Computer Programming in 100 Easy Lessons#65/100: Rotation Estimation, n digits accuracy? || Quantum Computer Programming in 100 Easy LessonsBasics of Communication Complexity || @ CMU || Lecture 23a of CS Theory Toolkit#15/100: Hadamard is unitary... || Quantum Computer Programming in 100 Easy Lessons
Ryan ODonnell |

Expander Graph Constructions || @ CMU || Lecture 16d of CS Theory Toolkit

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER