Programs
Fall 2014

Algorithmic Spectral Graph Theory

Aug. 21Dec. 19, 2014

Spectral methods have become a fundamental tool with a broad range of applications across computer science. These techniques have had a significant impact on several areas including machine learning, data mining, web search and ranking, scientific computing and computer vision. Moreover, from expander graphs and pseudorandomness, to the study of rapid mixing of Markov chains, to the use of spectral partitioning in approximation algorithms—understanding the eigenvalues and eigenvectors of the adjacency matrix (and the Laplacian) of graphs has become a standard method in every theorist’s toolkit.

Recent years have seen several exciting applications of spectral graph theory in the theory of computing. This includes work on fast solvers for linear systems, graph sparsification, local random walks, and subsequent combinatorial applications to computing maximum flows. Emerging connections between graph expansion, graph spectra and semi-definite programming hierarchies are playing a significant role in approximation algorithms and work on the Unique Games Conjecture. Newly discovered relationships between higher eigenvalues of graphs and spectral partitioning promise to create further interplay between theoretical analysis and widely employed heuristics.

This program addresses the use of spectral methods in confronting a number of fundamental open problems in the theory of computing, while at the same time exploring applications of newly developed spectral techniques to a diverse array of areas.

Organizers:

James R. Lee (University of Washington; co-chair), Prasad Raghavendra (UC Berkeley; co-chair), Ravi Kannan (Microsoft Research India), Jitendra Malik (UC Berkeley), Gary Miller (Carnegie Mellon University), Luca Trevisan (Simons Institute, UC Berkeley)

Long-Term Participants (including Organizers):

Alexandr Andoni (MIcrosoft Research), Peter Bartlett (UC Berkeley), Moses Charikar (Stanford University), Kamalika Chaudhuri (UC San Diego), Fan Chung (UC San Diego), Ronen Eldan (Microsoft Research), Ron Graham (UC San Diego), Nick Harvey (University of British Columbia), Dorit Hochbaum (UC Berkeley), Ravi Kannan (Microsoft Research India), Alexandra Kolla (University of Illinois at Urbana-Champaign), Risi Kondor (University of Chicago), Ioannis Koutis (University of Puerto Rico), Lap-Chi Lau (The Chinese University of Hong Kong), James R. Lee (University of Washington; co-chair), Elon Lindenstrauss (Hebrew University of Jerusalem), Nati Linial (Hebrew University of Jerusalem), Aleksander Mądry (Ecole Polytechnique Fédérale de Lausanne), Konstantin Makarychev (Microsoft Research), Yury Makarychev (Toyota Technological Institute at Chicago), Jitendra Malik (UC Berkeley), Marina Meila (University of Washington), Raghu Meka (UCLA), Gary Miller (Carnegie Mellon University), Lorenzo Orecchia (Boston University), Shayan Oveis Gharan (UC Berkeley), Pablo Parrilo (Massachusetts Institute of Technology), Yuval Rabani (Hebrew University of Jerusalem), Prasad Raghavendra (UC Berkeley; co-chair), Satish Rao (UC Berkeley), Margaret Reid-Miller (Carnegie Mellon University), Leonard Schulman (California Institute of Technology), Martha Sideri (Athens University of Economics and Business), Nikhil Srivastava (UC Berkeley), David Steurer (Cornell University), Kunal Talwar (), Prasad Tetali (Georgia Institute of Technology), Luca Trevisan (Simons Institute, UC Berkeley), Madhur Tulsiani (Toyota Technological Institute at Chicago), Caroline Uhler (IST Austria), Santosh Vempala (Georgia Institute of Technology), Nisheeth Vishnoi (Microsoft Research India)

Research Fellows:

Mihai Cucuringu (UCLA), Bundit Laekhanukit (McGill University), Yin Tat Lee (Massachusetts Institute of Technology), Aaron Sidford (Massachusetts Institute of Technology), Ali Sinop (Institute for Advanced Study, Princeton), He Sun (Max-Planck-Institut für Informatik), Li-Yang Tan (Columbia University; Microsoft Research Fellow)

Visiting Graduate Students and Postdocs:

Nima Anari (UC Berkeley), Jonah Brown-Cohen (UC Berkeley), Samuel Hopkins (Cornell University), Fotis Iliopoulos (UC Berkeley), Marc Khoury (UC Berkeley), Tsz Chiu Kwok (University of Washington), Jakub Pachocki (Carnegie Mellon University), Christos-Alexandros Psomas (UC Berkeley), Aviad Rubinstein (UC Berkeley), Aaron Schild (UC Berkeley), Tselil Schramm (UC Berkeley), Jonathan Shi (Cornell University), Seung Woo Shin (UC Berkeley), Shen Chen Xu (Carnegie Mellon University)

Workshops

Aug. 26Aug. 29, 2014

Organizers:

James R. Lee (University of Washington), Prasad Raghavendra (UC Berkeley)
Sep. 22Sep. 26, 2014

Organizers:

Fan Chung (UC San Diego), Pablo Parrilo (Massachusetts Institute of Technology), David Steurer (Cornell University)
Oct. 27Oct. 31, 2014

Organizers:

Misha Belkin (Ohio State University; co-chair), James R. Lee (University of Washington; co-chair), Mauro Maggioni (Duke University), Gary Miller (Carnegie Mellon University)
Dec. 1Dec. 5, 2014

Organizers:

Jon Kelner (Massachusetts Institute of Technology; chair), Dan Spielman (Yale University), Shang-Hua Teng (University of Southern California)
Dec. 15Dec. 18, 2015

Organizers:

James R. Lee (University of Washington), Prasad Raghavendra (UC Berkeley)

Program image by James R. Lee.  The image shows a spectral embedding of a triangulation of the Greek letter lambda; it was drawn using the first two non-trivial eigenvectors of the Laplacian.