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 that 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 on a boot camp and three workshops:

  1. Local to Global Principles

  2. Probabilistic Phenomena on Graphs, Groups, and Manifolds

  3. Beyond Graph Laplacians

Further details appear in the workshop descriptions.

Organizers: Nalini Anantharaman (Collège de France), Charles Bordenave (CNRS and Aix-Marseille Université), Lap Chi Lau (University of Waterloo), Sidhanth Mohanty (UC Berkeley), Doron Puder (Tel Aviv University), Nikhil Srivastava (UC Berkeley)

Long-Term Participants (tentative): Aida Abiad (Eindhoven University of Technology), Nikhil Bansal (University of Michigan), Claire Burrin (University of Zurich), Charles Bordenave (CNRS), Pietro Caputo (Roma Tre University), Gil Cohen (Tel Aviv University), Nick Cook (Duke University), Sean Eberhard (University of Warwick), Joel Friedman (University of British Columbia), Reza Gheissari (Northwestern University), Alice Guionnet (Lyon), Jiaoyang Huang (University of Pennsylvania), Martin Kassabov (Cornell University), Tali Kaufman (Bar-Ilan University), Alexandra Kolla (UC Santa Cruz), Peter Kuchment (Texas A&M), Lap Chi Lau (University of Waterloo), Nathan Linial (Hebrew University), Wencai Liu (Texas A&M), Kuikui Liu (MIT), Shiping Liu (USTC), Raghu Meka (UCLA), Sidhanth Mohanty (UC Berkeley), Tatiana Nagnibeda (University of Geneva), Asaf Nachmias (Tel Aviv University), Hariharan Narayanan (TIFR), Bram Petri (Sorbonne University), Doron Puder (Tel Aviv University), Zeev Rudnick (Tel Aviv University), Mostafa Sabri (NYU), Jenya Sapir (Binghamton University), Salil Vadhan (Harvard University), Tselil Schramm (Stanford), Makrand Sinha (UIUC), Joe Thomas (Durham), Yizhe Zhu (USC)