Jonathan Kelner (Massachusetts Institute of Technology)
Yiannis Koutis (University of Puerto Rico)
Gary Miller (Carnegie Mellon University)
Description
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.
Registration: Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond Workshop
11th Floor Collaborative Space
8:55 - 9:00
Welcome
ICERM Director
11th Floor Lecture Hall
9:00 - 9:45
Efficient Solvers for Linear Systems in Graph Laplacians
Richard Peng, Massachusetts Institute of Technology
11th Floor Lecture Hall
10:00 - 10:30
Coffee/Tea Break
11th Floor Collaborative Space
10:30 - 11:15
Electrical Flows, Continuous Optimization, and the Maximum Flow Problem
Aleksander Madry, Ecole Polytechnique Federale De Lausanne
11th Floor Lecture Hall
11:30 - 12:15
Small Lifts of Expander Graphs are Expanding
Alexandra Kolla, Univeristy of Illinois at Urbana-Champaign
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
An L^p Theory of Sparse Graph Limits
Christian Borgs, Microsoft Research
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
The Power of Locality for Network Algorithms
Jennifer Chayes, Microsoft Research
11th Floor Lecture Hall
5:00 - 6:30
Welcome Reception
11th Floor Collaborative Space
Tuesday
April 8, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Random Walks as a Stable Analogue of Eigenvectors with Applications to Nearly-Linear-Time Graph Partitioning
Lorenzo Orecchia, Massachusetts Institute of Technology
11th Floor Lecture Hall
10:00 - 10:30
Coffee/Tea Break
11th Floor Collaborative Space
10:30 - 11:15
Graph Sparsification
Debmalya Panigrahi, Duke University
11th Floor Lecture Hall
11:30 - 12:15
Heat Kernel Pagerank as a Linear Solver and Applications to Consensus Problems
Olivia Simpson, University of California, San Diego
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
Computations on Graph Laplacians
Erik Boman, Sandia National Laboratories
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
Poster 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
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
A simple parallel algorithm for spectral graph sparsification
Yiannis Koutis, University of Puerto Rico
11th Floor Lecture Hall
10:00 - 10:30
Coffee/Tea Break
11th Floor Collaborative Space
10:30 - 11:15
A Simple, Electrical, Gradient Descent Algorithm for Approximate Max Flow
Nikhil Srivastava, Microsoft Research India
11th Floor Lecture Hall
11:30 - 12:15
Guaranteed Tensor Decomposition through Alternating Rank-1 Updates
Anima Anandkumar, University of California, Irvine
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
Faster Algorithms via Approximation Theory
Nisheeth Vishnoi, Microsoft Research India
11th Floor Lecture Hall
3:00 - 5:20
Optimization Algorithms for Planar Graphs (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
10th Floor Classroom
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
Approximate Spectral Clustering via Randomized Sketching
Christos Boutsidis, Yahoo! Labs, New York
11th Floor Lecture Hall
Thursday
April 10, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
A simple algorithm for finding clusters in a random environment
Van Vu, Yale University
11th Floor Lecture Hall
10:00 - 10:30
Coffee/Tea Break
11th Floor Collaborative Space
10:30 - 11:15
Anti-differentiating approximation alogrithms for min-cuts and new relationships between Page Rank, spectral, and localized flow
David Gleich, Purdue University
11th Floor Lecture Hall
11:30 - 12:15
Spectral partitioning and higher-order Cheeger inequalities
James Lee, University of Washington
11th Floor Lecture Hall
12:30 - 12:45
Group Photo
11th Floor Lecture Hall
12:45 - 2:30
Break for Lunch
2:30 - 3:15
Improved Cheeger's Inequality
Shayan Oveis-Gharan, Stanford University
11th Floor Lecture Hall
3:30 - 3:30
Please take a moment to complete the survey that was distributed by email.
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
Open Problems Session
11th Floor Lecture Hall
Friday
April 11, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Faster Subset Selection for Matrices and Applications
Haim Avron, IBM Corporation
11th Floor Lecture Hall
10:00 - 10:30
Coffee/Tea Break
11th Floor Collaborative Space
10:30 - 11:15
Large-scale Computations of Edge-Importance Measures
Evimaria Terzi, Boston University
11th Floor Lecture Hall
11:30 - 12:15
TBA
John Kelner, Massachusetts Institute of Technology