About

Spectral graph theory within theoretical computer science has largely focused on the graph Laplacian. This workshop will consider other operators — such as Schrödinger operators, magnetic Laplacians, and Kikuchi matrices — on graphs as well as other spaces — such as manifolds, metric graphs, and hypergraphs. 
 

New questions arise in this broader context. For example, quantum ergodicity is a term borrowed from the field of quantum chaos, referring to a form of delocalization of eigenfunctions of a Schrödinger operator. This notion was first transposed to the case of the Laplacian on regular graphs by Anantharaman-LeMasson, and later generalized to the case of non-regular graphs, and metric graphs. So far, quantum ergodicity has been proven under the assumption that the graphs are expanders, have few short cycles, and converge to an infinite limiting tree having purely absolutely continuous spectrum. Studying quantum ergodicity beyond these settings is widely open, and the algorithmic implications of it remain unexplored.
 

Are there ways to reduce spectral questions on manifolds to those on graphs and vice versa? At present there is an analogy between graphs and manifolds, but quantitative bounds comparing their spectral features are lacking. Developing such bounds is an avenue towards new theorems in both settings as well as provably efficient algorithms for spectral computations on manifolds, which are also underdeveloped.

Chairs/Organizers