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


Tuesday, Aug. 26Friday, Aug. 29, 2014


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


Boaz Barak (Harvard University; chair), Fan Chung (UC San Diego), Pablo Parrilo (Massachusetts Institute of Technology), David Steurer (Cornell University)
Monday, Oct. 27Friday, Oct. 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)
Monday, Dec. 1Friday, Dec. 5, 2014


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