2008 AMS Levi L. Conant Prize Recipient
EXPANDER GRAPHS: —A PLAYGROUND FOR ALGEBRA, GEOMETRY, COMBINATORICS, AND COMPUTER SCIENCE
Expander graphs are extremely useful objects. In computer science, their applications range from network design, computational, derandomization error correction, data organization, and more. In mathematics they are used in topology, group theory, game theory, information theory, and naturally, graph theory. I plan to explain what expanders and their basic properties are, and survey the quest to explicitly construct them. I’ll focus on the recent combinatorial constructions, via the “zig-zag” product, and how these can go beyond the bounds achieved by algebraic methods. I'll also demonstrate some of the applications.
This talk is accessible to graduate students with no special background in Math and Computer Science.
Avi Wigderson received his BSc in computer science from Technion in 1980, and his PhD from Princeton in 1983. He served on the faculty at the Hebrew University in Jerusalem from 1986 to 2003, and is currently a member of the mathematics faculty at the Institute for Advanced Study at Princeton. His research interests lie principally in complexity theory, algorithms, randomness, and cryptography. His honors include the Nevanlinna Prize for outstanding contributions in mathematical aspects of information sciences (1994), the ICM Plenary Lecture in Madrid, Spain (2006), the AMS Conant Prize in 2008, and the Gödel Prize in 2009.