Organizing Committee
- Jonathan Kelner
Massachusetts Institute of Technology - Ioannis Koutis
University of Puerto Rico - Gary Miller
Carnegie Mellon University
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
Talks will be presented virtually or in-person as indicated in the schedule below.
- Speaker
- Poster Presenter
- Attendee
- Virtual Attendee
-
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
-
Erik Boman
Sandia National Laboratories
-
Christian Borgs
Microsoft
-
Christos Boutsidis
Yahoo! Inc.
-
Yixin Cao
Hungarian Academy of Sciences (MTA)
-
Jennifer Chayes
Microsoft
-
Michael Cohen
Massachusetts Institute of Technology
-
Mihai Cucuringu
University of California, Los Angeles
-
Thomas Dickerson
Brown University
-
Michela Egidi
University of Durham
-
Lledo 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
Universite 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
-
Ioannis 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
EPFL
-
Ahmad Mahmoody
Brown University
-
William Martin
Worcester Polytechnic Institute
-
Claire Mathieu
Ecole Normale Suptrieure
-
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
University of Washington, St. Louis
-
Benjamin Raphael
Brown University
-
Amanda Redlich
Bowdoin College
-
Igor Rivin
Temple University
-
Scott Roche
Northeastern University
-
Sushant Sachdeva
Yale University
-
Bernd Schroeder
Louisiana Tech University
-
Olivia Simpson
UC 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
Harvard 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
Ecole Normale Suptrieure
-
Yao Zhu
Purdue University