Organizing Committee
Abstract

Spectral graph theory, which studies how the eigenvalues and eigenvectors of the graph Laplacian (and other related matrices) interact with the combinatorial structure of a graph, is a classical tool in both the theory and practice of algorithm design. The success of this approach has been rooted in the efficiency with which eigenvalues and eigenvectors can be computed, and in the surprisingly large number of ways that a graph's properties are connected to the Laplacian's spectrum---particularly to the value of its second smallest eigenvalue, λ2.

However, while the eigenvalues and eigenvectors of the Laplacian capture a striking amount of the structure of the graph, they certainly do not capture all of it. Recent work in the field suggests that we have only scratched the surface of what can be done if we are willing to broaden our investigation to include more general linear-algebraic properties of the matrices we associate to graphs.

A particularly fruitful example of this has been the study of Laplacian linear systems, where the interplay between linear algebra and graph theory has led to progress in both fields. On the one hand, researchers have used the combinatorial structure of the corresponding graphs to facilitate the solution of these linear systems, resulting in solvers that run in nearly-linear time. On the other hand, one can use these linear systems to describe the behavior of electrical flows on a graph, which has provided a powerful new primitive for algorithmic graph theory. This interaction has already led to improved algorithmic results for many of the basic problems in algorithmic graph theory, including finding maximum flows and minimum cuts, solving traveling salesman problems, sampling random trees, sparsifying graphs, computing multicommodity flows, and approximately solving a wide range of general clustering and partitioning problems. In addition, researchers have recently shown how to exploit a wide range of other algebraic properties of matrices associated to graphs, such as the threshold rank, cut norm, sensitivity to perturbation, or hypercontractivity of the eigenspaces, to achieve impressive algorithmic results.

In this workshop, we will bring researchers together to study and advance this new emerging frontier in algorithmic graph theory.

Confirmed Speakers & Participants

Workshop Schedule

Monday, April 7, 2014
TimeEventLocationMaterials
8:30 - 8:55Registration: Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond Workshop11th Floor Collaborative Space 
8:55 - 9:00Welcome - ICERM Director11th Floor Lecture Hall 
9:00 - 9:45Efficient Solvers for Linear Systems in Graph Laplacians - Richard Peng, Massachusetts Institute of Technology11th Floor Lecture Hall
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15Electrical Flows, Continuous Optimization, and the Maximum Flow Problem - Aleksander Madry, Ecole Polytechnique Federale De Lausanne11th Floor Lecture Hall
11:30 - 12:15Small Lifts of Expander Graphs are Expanding - Alexandra Kolla, Univeristy of Illinois at Urbana-Champaign11th Floor Lecture Hall
12:30 - 2:30Break for Lunch  
2:30 - 3:15An L^p Theory of Sparse Graph Limits - Christian Borgs, Microsoft Research11th Floor Lecture Hall
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45The Power of Locality for Network Algorithms - Jennifer Chayes, Microsoft Research11th Floor Lecture Hall
5:00 - 6:30Welcome Reception11th Floor Collaborative Space 
Tuesday, April 8, 2014
TimeEventLocationMaterials
9:00 - 9:45Random Walks as a Stable Analogue of Eigenvectors with Applications to Nearly-Linear-Time Graph Partitioning - Lorenzo Orecchia, Massachusetts Institute of Technology11th Floor Lecture Hall
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15Graph Sparsification - Debmalya Panigrahi, Duke University11th Floor Lecture Hall
11:30 - 12:15Heat Kernel Pagerank as a Linear Solver and Applications to Consensus Problems - Olivia Simpson, University of California, San Diego11th Floor Lecture Hall
12:30 - 2:30Break for Lunch  
2:30 - 3:15Computations on Graph Laplacians - Erik Boman, Sandia National Laboratories11th Floor Lecture Hall
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45Poster Session Preview - Michela Egidi, Durham University; Emilie Hogan, Pacific Northwest National Laboratory; Franklin H. J. Kenter, Rice University; Shiping Liu, University of Durham; Francois Meyer, University of Colorado; Bernd Schroeder, Louisiana Tech University; Yao Zhu, Purdue University;11th Floor Lecture Hall 
Wednesday, April 9, 2014
TimeEventLocationMaterials
9:00 - 9:45A simple parallel algorithm for spectral graph sparsification - Yiannis Koutis, University of Puerto Rico11th Floor Lecture Hall
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15A Simple, Electrical, Gradient Descent Algorithm for Approximate Max Flow - Nikhil Srivastava, Microsoft Research India11th Floor Lecture Hall
11:30 - 12:15Guaranteed Tensor Decomposition through Alternating Rank-1 Updates - Anima Anandkumar, University of California, Irvine11th Floor Lecture Hall
12:30 - 2:30Break for Lunch  
2:30 - 3:15Faster Algorithms via Approximation Theory - Nisheeth Vishnoi, Microsoft Research India11th Floor Lecture Hall
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course) - Phil Klein, Brown University and Claire Mathieu, Brown University10th Floor Classroom 
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45Approximate Spectral Clustering via Randomized Sketching - Christos Boutsidis, Yahoo! Labs, New York11th Floor Lecture Hall
7:00 - 8:30Poster Session and Dessert Reception11th Floor Collaborative Space and Lecture Hall 
Thursday, April 10, 2014
TimeEventLocationMaterials
9:00 - 9:45A simple algorithm for finding clusters in a random environment - Van Vu, Yale University11th Floor Lecture Hall
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15Anti-differentiating approximation alogrithms for min-cuts and new relationships between Page Rank, spectral, and localized flow - David Gleich, Purdue University11th Floor Lecture Hall
11:30 - 12:15Spectral partitioning and higher-order Cheeger inequalities - James Lee, University of Washington11th Floor Lecture Hall
12:30 - 12:45Group Photo11th Floor Lecture Hall 
12:45 - 2:30Break for Lunch  
2:30 - 3:15Improved Cheeger's Inequality - Shayan Oveis-Gharan, Stanford University11th Floor Lecture Hall
3:30 - 3:30Please take a moment to complete the survey that was distributed by email.  
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45Open Problems Session11th Floor Lecture Hall 
Friday, April 11, 2014
TimeEventLocationMaterials
9:00 - 9:45Faster Subset Selection for Matrices and Applications - Haim Avron, IBM Corporation11th Floor Lecture Hall
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15Large-scale Computations of Edge-Importance Measures - Evimaria Terzi, Boston University11th Floor Lecture Hall
11:30 - 12:15TBA - John Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall 
12:30 - 2:30Break for Lunch  
2:30 - 3:15Open Problems for Real Data11th Floor Lecture Hall 
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45TBA - TBA11th Floor Lecture Hall 

Associated Semester Workshops

Network Science and Graph Algorithms
Semidefinite Programming and Graph Algorithms
Stochastic Graph Models

Research Clusters

Lecture Videos