My Favorite Expanders | Richard M. Karp Distinguished Lecture

Ryan O’Donnell presents simple, strongly explicit expander graph constructions and explains how they can be used to build super-expanders.

Ryan O’Donnell (Carnegie Mellon University) 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.