Algebraic and Spectral Graph Theory (16w5111)

Arriving in Banff, Alberta Sunday, July 31 and departing Friday August 5, 2016


(University of Waterloo)

(University of British Columbia)

Nikhil Srivastava (University of California, Berkeley)

(University of Washington)


The goals of the workshop are as follows:

(1) To bring together researchers in the fields of spectral graph theory and algebraic graph theory, and to stimulate the exchange of ideas and techniques between the two groups. The basic objects of study in spectral graph theory have traditionally been eigenvalues and eigenvectors; the same is true of spectral algorithms. On the other hand, recent breakthroughs on Ramanujan graphs and the Kadison-Singer problem are instead based on analyzing characteristic polynomials, which have received intensive study in the algebraic graph theory community. We anticipate many benefits of promoting interaction between the spectral and algebraic graph theory researchers.

(2) To enlarge everybody’s notions of what algebraic and spectral graph theory can mean. We have invited several researchers (Friedman, Gilbert, Godsil, Kaufman-Halman, Lindenstrauss, Lubotzky) who currently work on promising frontiers of this field, such as more general physical processes on graphs (quantum walks, scattering, wave equation), delocalization of eigenvectors and connections to ergodic theory, and spectral theory of higher simplicial complexes.

(3) To include many younger researchers, and foster a relaxed interaction with established researchers. At present, we have informed only a small number of young researchers. If the workshop is approved, then we will invite other young researchers. Our goal is to have a third of the workshop participants from this group.

Timeliness and appropriateness of the workshop

There are three overarching themes on which we focus. Each of these has taken shape over the past few years, and the potential for significant progress is ripe. This is an opportune time for a workshop that will foster interaction and crystalize an agenda for future work.

1. Linear-time Laplacian systems solvers and applications to fast algorithms for combinatorial problems. Since Spielman and Teng gave the first near-linear time algorithms for solving sparse, diagonally-dominant linear systems, progress has been rampant. New algorithms have led to advances in many areas of computer science. A prominent example is the recent work on maximum flows which uses these solvers as a subroutine to yield the first improvements on running times that have stood for 35 years. Even more recently, this line of work has led to significant new results in interior point methods for solving linear programs.

2. Sparsification, interlacing polynomials, and the Kadison-Singer problem. The work of Marcus, Spielman, and Srivastava--which itself was inspired by the push for faster Laplacian solvers--has shown the relevance of algebraic graph theory to the modern spectral theory of graphs. As an example of the kind of connection the proposed workshop seeks to encourage, it seems likely that these algebraic techniques could lend insight to the “thin-trees conjecture” from classical graph theory. In particular, this provides a path to understanding the complexity of the asymmetric traveling salesman problem.

3. Spectral geometry of graphs, small set expansion, and the unique games conjecture. It has long been known that the eigenvectors of the Laplacian encode information on the cut structure of graphs. But it has only become apparent recently that an intimate relationship exists, in generality, throughout the spectrum. These “higher order” spectral phenomena have been employed to mount an attack on the unique games conjecture, a central open problem in computational complexity. On the other side, the extent to which the expansion and spectral profile disassociate at large energies has inspired the “short code” construction. This has led, for example, to new progress on the Goemans-Linial conjecture in metric geometry. A major goal is to identify “certificates” for graph expansion (e.g., log-Sobolev inequalities) that cannot be efficiently searched for. Such certificates would provide the seeds for exhibiting computational hardness.