Home

Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond
(April 7-11, 2014)


CLICK HERE TO PARTICIPATE
Review of applications will begin on December 15, 2013
Organizing Committee
  • 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.

  • Rediet Abebe
    (University of Cambridge)
  • Monther Alfuraidan
    (King Fahd University of Petroleum and Minerals)
  • Zeyuan Allen-Zhu
    (Massachusetts Institute of Technology)
  • Anima Anandkumar*
    (University of California, Irvine)
  • John Augustine
    (Indian Institute of Technology)
  • Chen Avin
    (Ben Gurion University of the Negev)
  • Haim Avron*
    (IBM Corporation)
  • Frank Bauer
    (Harvard University)
  • Petra Berenbrink
    (Simon Fraser University)
  • Daniel Bienstock
    (Columbia University)
  • Erik Boman*
    (Sandia National Laboratories)
  • Christian Borgs *
    (Microsoft Research)
  • Christos Boutsidis*
    (Yahoo! Inc.)
  • Yixin Cao
    (Hungarian Academy of Sciences (MTA))
  • Jennifer Chayes *
    (Microsoft Research)
  • Michael Cohen
    (Massachusetts Institute of Technology)
  • Mihai Cucuringu
    (University of California, Los Angeles)
  • Thomas Dickerson
    (Brown University)
  • Michela Egidi
    (Durham University)
  • Lledó Esquerra-Ortells
    (University of Colorado)
  • Pedro Felzenszwalb
    (Brown University)
  • Kyle Fox
    (University of Illinois at Urbana-Champaign)
  • Eli Fox-Epstein
    (Brown University)
  • Nathanaël François
    (Université de Paris VII (Denis Diderot))
  • David Gillman
    (New College of Florida)
  • David Gleich*
    (Purdue University)
  • Mamikon Gulian
    (Brown University)
  • Bruce Hendrickson
    (Sandia National Laboratories)
  • Emilie Hogan
    (Pacific Northwest National Laboratory)
  • Majid Janzamin
    (University of California, Irvine)
  • Jonathan Kelner *
    (Massachusetts Institute of Technology)
  • Yvonne Kemper
    (National Institute of Standards and Technology)
  • Franklin Kenter
    (Rice University)
  • Richard Kenyon
    (Brown University)
  • Philip Klein
    (Brown University)
  • Caroline Klivans
    (Brown University)
  • Alexandra Kolla*
    (University of Illinois at Urbana-Champaign)
  • Yiannis Koutis *
    (University of Puerto Rico)
  • Rasmus Kyng
    (Yale University)
  • Matthew Langston
    (Reservoir Labs Inc)
  • James Lee*
    (University of Washington)
  • Gabor Lippner
    (Harvard University)
  • Shiping Liu
    (University of Durham)
  • Aleksander Madry*
    (École Polytechnique Fédérale de Lausanne (EPFL))
  • Ahmad Mahmoody
    (Brown University)
  • William Martin
    (Worcester Polytechnic Institute)
  • Claire Mathieu
    (École Normale Supérieure)
  • Charalampos Mavroforakis
    (Boston University)
  • Patrick McDonald
    (New College of Florida)
  • David Meierfrankenfeld
    (Brown University)
  • Francois Meyer
    (University of Colorado)
  • Gary Miller
    (Carnegie Mellon University)
  • Sobhan Naderi Parizi
    (Brown University)
  • Krishna Nand
    (Brown University)
  • Danupon Nanongkai
    (Nanyang Technological University)
  • Lorenzo Orecchia*
    (Massachusetts Institute of Technology)
  • Shayan Oveis-Gharan*
    (Stanford University)
  • Jakub Pachocki
    (Carnegie Mellon University)
  • Gopal Pandurangan
    (Nanyang Technological University)
  • Debmalya Panigrahi *
    (Duke University)
  • Richard Peng*
    (Massachusetts Institute of Technology)
  • Lam Pham
    (Yale University)
  • Mason Porter
    (University of Oxford)
  • Saad Quader
    (University of Connecticut)
  • Sanjay Ramassamy
    (Brown University)
  • Anup Rao
    (Yale University)
  • Ben Raphael
    (Brown University)
  • Amanda Redlich
    (Bowdoin College)
  • Igor Rivin
    (Temple University)
  • Scott Roche
    (Northeastern University)
  • Sushant Sachdeva
    (Yale University)
  • Bernd Schroeder
    (Louisiana Tech University)
  • Oliva Simpson*
    (University of California, San Diego)
  • Ali Sinop
    (Institute for Advanced Study)
  • Jon Sjogren
    (Towson State University)
  • Nikhil Srivastava*
    (Microsoft Research India)
  • He Sun
    (Max-Planck-Institut für Informatik)
  • Christino Tamon
    (Clarkson University)
  • Evimaria Terzi*
    (Boston University)
  • Charalampos Tsourakakis
    (Carnegie Mellon University)
  • Lara Ruth Turner
    (University of Vienna )
  • Eli Upfal
    (Brown University)
  • Nisheeth Vishnoi*
    (Microsoft Research India)
  • Van Vu*
    (Yale University)
  • Shen Chen Xu
    (Carnegie Mellon University)
  • Grigory Yaroslavtsev
    (Pennsylvania State University)
  • Neal Young
    (University of California, Riverside)
  • Luca Zanetti
    (Universität des Saarlandes)
  • Hang Zhou
    (École Normale Supérieure)
  • Yao Zhu
    (Purdue University)
MondayApril 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 8:55Registration: Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond Workshop11th Floor Collaborative Space
8:55 - 9:00WelcomeICERM Director11th Floor Lecture Hall
9:00 - 9:45Efficient Solvers for Linear Systems in Graph LaplaciansRichard Peng, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Electrical Flows, Continuous Optimization, and the Maximum Flow ProblemAleksander Madry, Ecole Polytechnique Federale De Lausanne11th Floor Lecture Hall
PDF
11:30 - 12:15Small Lifts of Expander Graphs are ExpandingAlexandra Kolla, Univeristy of Illinois at Urbana-Champaign11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15An L^p Theory of Sparse Graph LimitsChristian Borgs, Microsoft Research11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45The Power of Locality for Network AlgorithmsJennifer Chayes, Microsoft Research11th Floor Lecture Hall
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayApril 8, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Random Walks as a Stable Analogue of Eigenvectors with Applications to Nearly-Linear-Time Graph PartitioningLorenzo Orecchia, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Graph SparsificationDebmalya Panigrahi, Duke University11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Heat Kernel Pagerank as a Linear Solver and Applications to Consensus ProblemsOlivia Simpson, University of California, San Diego11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15Computations on Graph LaplaciansErik Boman, Sandia National Laboratories11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Poster Session PreviewMichela 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

WednesdayApril 9, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45A simple parallel algorithm for spectral graph sparsificationYiannis Koutis, University of Puerto Rico11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15A Simple, Electrical, Gradient Descent Algorithm for Approximate Max FlowNikhil Srivastava, Microsoft Research India11th Floor Lecture Hall
PDF
11:30 - 12:15Guaranteed Tensor Decomposition through Alternating Rank-1 UpdatesAnima Anandkumar, University of California, Irvine11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15Faster Algorithms via Approximation TheoryNisheeth Vishnoi, Microsoft Research India11th Floor Lecture Hall
PDF
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 SketchingChristos Boutsidis, Yahoo! Labs, New York11th Floor Lecture Hall
PDF
PDF

ThursdayApril 10, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45A simple algorithm for finding clusters in a random environmentVan Vu, Yale University11th Floor Lecture Hall
PDF
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 flowDavid Gleich, Purdue University11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Spectral partitioning and higher-order Cheeger inequalitiesJames Lee, University of Washington11th Floor Lecture Hall
PDF
12:30 - 12:45Group Photo11th Floor Lecture Hall
12:45 - 2:30Break for Lunch
2:30 - 3:15Improved Cheeger's InequalityShayan Oveis-Gharan, Stanford University11th Floor Lecture Hall
PDF
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

FridayApril 11, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Faster Subset Selection for Matrices and ApplicationsHaim Avron, IBM Corporation11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Large-scale Computations of Edge-Importance MeasuresEvimaria Terzi, Boston University11th Floor Lecture Hall
PDF
11:30 - 12:15TBAJohn 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:45TBATBA11th Floor Lecture Hall