My Favorite Expanders | Richard M. Karp Distinguished Lecture @SimonsInstitute
My Favorite Expanders | Richard M. Karp Distinguished Lecture  @SimonsInstitute
Uploaded September 2026 | Updated November 2026, 2 days ago
Ryan O’Donnell (Carnegie Mellon University)
https://simons.berkeley.edu/talks/2026-09-29
Richard M. Karp Distinguished Lecture

Expander graphs are sparse graphs for which, whenever you split the graph into two parts, the number of edges going between the parts is proportional to the size of the smaller part. There are extremely simple, strongly explicit expander families whose analysis requires only a tiny bit of group theory. This fact is perhaps not so widely known. In this lecture, Ryan O’Donnell will show some of these constructions/analyses, and also indicate how they can be used to get even stronger kinds of expanders, such as “super-expanders,” and “non-sofic property (T) groups.”

Ryan O’Donnell is a Professor of Computer Science at Carnegie Mellon University. He received his BSc from the University of Toronto in 1999, and his PhD in applied mathematics from MIT in 2003, where he was advised by Madhu Sudan. His research interests include complexity theory, quantum computation, and spectral graph theory. He is the author of the book Analysis of Boolean Functions.

The Richard M. Karp Distinguished Lectures were created in Fall 2019 to celebrate the role of Simons Institute Founding Director Dick Karp in establishing the field of theoretical computer science, formulating its central problems, and contributing stunning results in the areas of computational complexity and algorithms. Formerly known as the Simons Institute Open Lectures, the series features visionary leaders in the field of theoretical computer science and is geared toward a broad scientific audience.

The lecture recording URL will be emailed to registered participants. This URL can be used for access to the livestream and recorded lecture. Lecture recordings will be publicly available on SimonsTV about five days following each presentation unless otherwise noted.
My Favorite Expanders | Richard M. Karp Distinguished LectureMatching Correlated Random Geometric GraphsFault-Tolerant Quantum Computation with Adversarial ErrorsApollonian random manifolds and their bass notesSampling from the Sherrington-Kirkpatrick model up to β<1/2Coboundary Expansion and Locally Testable Codes (Part 2)The BRRY analysis of the INW generator is optimalTalk by Hsin-Yuan Huang (Oratomic, Caltech)Strong Spatial Mixing for Colorings on Trees and its Algorithmic ApplicationsSpectral gap of 1D quantum Gibbs samplersSharp Bounds on Ground State Energy of the SYK ModelRare event analysis via stochastic optimal control
Simons Institute for the Theory of Computing |

My Favorite Expanders | Richard M. Karp Distinguished Lecture

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER