Expanders are highly-connected sparse graphs widely used in Computer Science, in areas ranging from parallel computation to complexity theory and cryptography. 2008 marks two important anniversaries in the development of the theory of expander graphs: the field was born 35 years ago, in 1973, when, following Pinsker’s observation that random regular graphs are expanders, Margulis gave the first explicit construction using Kazhdan’s Property T; fifteen years later, in 1988, Margulis, Lubotzky, Phillips and Sarnak constructed Ramanujan graphs (optimal expanders form spectral point of view) using deep results from the theory of automorphic forms. After a period of steady development, the theory of expander graphs has undergone explosive growth over the past several years: on the one hand, a number of long-standing problems have been resolved; on the other hand, several completely new and unexpected lines of development have emerged. Currently expanders are at the center of a great deal of research involving mutually beneficial interactions between computer science, number theory, combinatorics, group theory, and geometry. The workshop will bring together researchers from these fields to survey the progress made, outline the challenges ahead, and generate further collaborations.
Alexander Gamburd
(University of California, Santa Cruz (UC Santa Cruz))
Alexander Lubotzky
(The Hebrew University of Jerusalem)
Audrey Terras
(University of California, San Diego (UCSD))
Avi Wigderson
(Institute for Advanced Study)
Copyright. All Rights Reserved.