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.


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), 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)


Aug. 26Aug. 29, 2014


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


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


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


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


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.

Past Internal Program Activities

Wednesday, December 17 2:00 pm3:00 pm
Yuval Rabani (Hebrew University of Jerusalem)
Monday, December 15 2:00 pm3:00 pm
Shayan Oveis Gharan (University of Washington)
Thursday, December 11 2:00 pm3:00 pm
He Sun (Max-Planck-Institut für Informatik)
Wednesday, December 10 3:15 pm4:15 pm
Ali Sinop (Institute for Advanced Study, Princeton)
Monday, December 8 1:30 pm2:30 pm
Elon Lindenstrauss (Hebrew University of Jerusalem)
Thursday, November 20 2:00 pm3:00 pm
Wednesday, November 19 2:00 pm3:00 pm
Yury Makarychev (Toyota Technological Institute at Chicago)
Tuesday, November 18 2:00 pm3:00 pm
Eugene Velcharynski (Lawrence Berkeley National Lab)
Thursday, November 13 4:00 pm5:00 pm
Leo Grady (Heartflow Inc.)
Thursday, November 13 2:00 pm3:00 pm
Alexandr Andoni (Microsoft Research)
Thursday, November 6 2:00 pm3:00 pm
Anand Louis (Princeton University)
Wednesday, November 5 3:15 pm4:15 pm
Zeyuan Allen-Zhu (Massachusetts Institute of Technology)
Tuesday, November 4 2:00 pm3:00 pm
Aish Fenton (Netflix)
Thursday, October 23 2:00 pm3:00 pm
Aaron Sidford (Massachusetts Institute of Technology)
Tuesday, October 21 2:00 pm3:00 pm
Ioannis Koutis (University of Puerto Rico)
Thursday, October 16 2:00 pm3:00 pm
Kunal Talwar (Microsoft Research)
Thursday, October 9 2:00 pm3:00 pm
Fan Chung (UC San Diego)
Thursday, October 2 2:00 pm3:00 pm
Nati Linial (Hebrew University of Jerusalem)
Tuesday, September 30 2:00 pm3:00 pm
Silvio Lattanzi (Google Research)
Thursday, September 18 4:30 pm6:30 pm
David Steurer (Cornell University)
Thursday, September 11 2:00 pm3:00 pm
Jakub Pachocki (Carnegie Mellon University)
Wednesday, September 3 5:00 pm
James Lee (University of Washington)
Tuesday, September 2 5:00 pm
James Lee (University of Washington)