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

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, April 7, 2014
TimeEventLocationMaterials
8:30 - 8:55am EDTRegistration: Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond Workshop11th Floor Collaborative Space 
8:55 - 9:00am EDTWelcome - ICERM Director11th Floor Lecture Hall 
9:00 - 9:45am EDTEfficient Solvers for Linear Systems in Graph Laplacians - Richard Peng, Massachusetts Institute of Technology11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTElectrical Flows, Continuous Optimization, and the Maximum Flow Problem - Aleksander Madry, Ecole Polytechnique Federale De Lausanne11th Floor Lecture Hall
11:30 - 12:15pm EDTSmall Lifts of Expander Graphs are Expanding - Alexandra Kolla, Univeristy of Illinois at Urbana-Champaign11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch  
2:30 - 3:15pm EDTAn L^p Theory of Sparse Graph Limits - Christian Borgs, Microsoft Research11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTThe Power of Locality for Network Algorithms - Jennifer Chayes, Microsoft Research11th Floor Lecture Hall
5:00 - 6:30pm EDTWelcome Reception11th Floor Collaborative Space 
Tuesday, April 8, 2014
TimeEventLocationMaterials
9:00 - 9:45am EDTRandom 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:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTGraph Sparsification - Debmalya Panigrahi, Duke University11th Floor Lecture Hall
11:30 - 12:15pm EDTHeat Kernel Pagerank as a Linear Solver and Applications to Consensus Problems - Olivia Simpson, University of California, San Diego11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch  
2:30 - 3:15pm EDTComputations on Graph Laplacians - Erik Boman, Sandia National Laboratories11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTPoster 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:45am EDTA simple parallel algorithm for spectral graph sparsification - Yiannis Koutis, University of Puerto Rico11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTA Simple, Electrical, Gradient Descent Algorithm for Approximate Max Flow - Nikhil Srivastava, Microsoft Research India11th Floor Lecture Hall
11:30 - 12:15pm EDTGuaranteed Tensor Decomposition through Alternating Rank-1 Updates - Anima Anandkumar, University of California, Irvine11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch  
2:30 - 3:15pm EDTFaster Algorithms via Approximation Theory - Nisheeth Vishnoi, Microsoft Research India11th Floor Lecture Hall
3:00 - 5:20pm EDTOptimization Algorithms for Planar Graphs (ongoing semester course) - Phil Klein, Brown University and Claire Mathieu, Brown University10th Floor Classroom 
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTApproximate Spectral Clustering via Randomized Sketching - Christos Boutsidis, Yahoo! Labs, New York11th Floor Lecture Hall
7:00 - 8:30pm EDTPoster Session and Dessert Reception11th Floor Collaborative Space and Lecture Hall 
Thursday, April 10, 2014
TimeEventLocationMaterials
9:00 - 9:45am EDTA simple algorithm for finding clusters in a random environment - Van Vu, Yale University11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTAnti-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:15pm EDTSpectral partitioning and higher-order Cheeger inequalities - James Lee, University of Washington11th Floor Lecture Hall
12:30 - 12:45pm EDTGroup Photo11th Floor Lecture Hall 
12:45 - 2:30pm EDTBreak for Lunch  
2:30 - 3:15pm EDTImproved Cheeger's Inequality - Shayan Oveis-Gharan, Stanford University11th Floor Lecture Hall
3:30 - 3:30pm EDTPlease take a moment to complete the survey that was distributed by email.  
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTOpen Problems Session11th Floor Lecture Hall 
Friday, April 11, 2014
TimeEventLocationMaterials
9:00 - 9:45am EDTFaster Subset Selection for Matrices and Applications - Haim Avron, IBM Corporation11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTLarge-scale Computations of Edge-Importance Measures - Evimaria Terzi, Boston University11th Floor Lecture Hall
11:30 - 12:15pm EDTTBA - John Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall 
12:30 - 2:30pm EDTBreak for Lunch  
2:30 - 3:15pm EDTOpen Problems for Real Data11th Floor Lecture Hall 
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTTBA - TBA11th Floor Lecture Hall 

Associated Semester Workshops

Network Science and Graph Algorithms
Image for "Network Science and Graph Algorithms"
Semidefinite Programming and Graph Algorithms
Image for "Semidefinite Programming and Graph Algorithms"
Stochastic Graph Models
Image for "Stochastic Graph Models"

Research Clusters

Lecture Videos