Expander Graphs

Institute: IAS     May 2006

A central computational theme is “parallel processing”: allowing a large number to processors to work simultaneously and thus potentially speed up computation. A major issue for this development is the architecture of the communication network among these processors. The problem of how to design such a network is translated into a mathematical problem of finding graphs called “expanders” which have a small number of edges but are still highly connected (these graphs have numerous applications beyond the one above).

In the late 80’s, Margulis, Lubotzky, Phillips and Sarnak have shown how deep results from the theory of automorphic forms can be applied to get solutions to such down to earth problems in computer science. This opened up some new exciting connections between the areas of number theory, representation theory, discrete mathematics and computer science.

To enable more bridges of this kind, a year long research program was set up at the Institute for Advanced Study in Princeton for the academic year 2005-2006 and was led by A. Lubotzky. During the year several more connections have been found and maybe even more surprisingly, the computer science payed off its debit to number theory: Bourgain, Gamburd and Sarnak showed how the concept of expanders originated in computer science leads to strong sieving results in number theory; opening the door to many more exciting results in number theory which were inaccessible previously.

The program led to a solution of few long standing problems, such as Y. Shalom’s proof of property (T) for the special linear group over polynomial rings, the work of Kassabov, Nikolov and Lubotzky showing that finite simple groups can be made into expanders. The work of Lackenby on connection between expanders and hyperbolic geometry shows another exciting interaction between pure mathematics and computer science.