About

Spectral graph theory is a central topic in theoretical computer science, with consequences in both algorithms and complexity. It belongs to a broader mathematical tradition which studies spectra of operators on more general spaces including groups and manifolds, which in turn relate to many other areas of mathematics such as mathematical physics, random matrices, number theory, and operator algebras.

Over the past decade, connections between these fields have been very fruitful. For instance, the theory of Markov chains has been revolutionized by ideas from high dimensional expansion, stochastic localization, and notions of curvature on graphs. Our understanding of random graphs and manifolds has advanced dramatically, in tandem with related developments in random matrix theory and free probability — which have in another direction led to progress in discrepancy theory. The theory of quantum chaos has inspired new ways to understand the eigenvectors of random and deterministic graphs.

This program seeks to explore these connections further, with the goal of transferring not only results and techniques, but also questions and research directions between the settings of graphs, manifolds, and groups, and between mathematics and computer science. The scientific content of the program is centered around a boot camp and three workshops:

  1. Local to Global Principles

  2. Probabilistic Phenomena on Graphs and Manifolds

  3. Beyond Graph Laplacians

Further details appear in the workshop descriptions.

Organizers: Nalini Anantharaman (College de France), Charles Bordenave (CNRS and Aix Universite Marseille), Doron Puder (Tel Aviv University), Lap Chi Lau (University of Waterloo), Nikhil Srivastava (UC Berkeley)

Long-Term Participants (tentative): Nikhil Bansal (University of Michigan), Gregory Berkolaiko (TAMU), Charles Bordenave (CNRS), Pietro Caputo (Roma Tre University), Sourav Chatterjeee (Stanford University), Gil Cohen (Tel Aviv University), Benoit Collins (Kyoto University), Alice Guionnet (Lyon), Svetlana Jitomirskaya (UC Berkeley), Tali Kaufman (Bar-Ilan University), Alexandra Kolla (UC Santa Cruz), Kuikui Liu (MIT), Michael Magee (Durham University), Raghu Meka (UCLA), Tatiana Nagnibeda (University of Geneva), Shayan Oveis Gharan (University of Washington), Narutaka Ozawa (RIMS), Bram Petri (Sorbonne University), Zeev Rudnick (Tel Aviv University), Justin Salez (Paris Dauphine University), Peter Sarnak (Princeton University), Salil Vadhan (Harvard University), Maciej Zworski (UC Berkeley)