Open Lecture — The Unreasonable Effectiveness of Spectral Graph Theory: A Confluence of Algorithms, Geometry, and Physics

Spectral geometry has long been a powerful tool in many areas of mathematics and physics. In a similar way, spectral graph theory has played an important role in algorithms. But the last decade has seen a revolution of sorts:  Fueled by fundamental computational questions, spectral methods have been challenged to address new kinds of problems, and have proved their worth by providing a remarkable set of new ideas and solutions.

Starting with a basic physical process (heat diffusion), we will recall how the evolution of the system can be understood in terms of eigenmodes and their associated eigenvalues. The physical view has immediate computational import; for instance, Google models its users as agents diffusing over the web graph. This family of ideas describes the "reasonable" effectiveness of spectral graph theory. But then we will see that spectral objects can also precisely describe other phenomena in a surprisingly unreasonable way. This will lead us to confront some of the most fundamental problems in algorithms and complexity theory from a spectral perspective.

The tendency in the talk will be toward highlighting progress (theorems) and mystery (conjectures) through pictures and animations.

Light refreshments will be served before the lecture at 3:30 p.m.