(University of California, Los Angeles)
(Massachusetts Institute of Technology)
Philip Klein (Brown University)
(CNRS, Ecole Normale Supérieure and Brown University)
David Shmoys (Cornell University)
Eli Upfal (Brown University)
[Image courtesy of Eli Upfal]
The study of computational problems on graphs has long been a central area of research in computer science. However, recent years have seen qualitative changes in both the problems to be solved and the tools
available to do so. Application areas such as computational biology, the web, social networks, and machine learning give rise to large graphs and complex statistical questions that demand new algorithmic ideas
and computational models. A wide variety of techniques are emerging for addressing these challenges: from semidefinite programming and combinatorial preconditioners.
In addition to three international conferences, the program will support several research clusters, concentrated periods of activity organized around a specific and timely approach to graph algorithms.
To participate in a research cluster please apply through the
semester program visitors
application. Indicate which research cluster you are applying to in the "other comments"
section of the application.
Research Cluster: Geometric analysis methods for graph algorithms (February 3-28, 2014)
Andrea Bertozzi (University of California, Los Angeles)
Thomas Laurent (Loyola Marymount University)
This working group will develop new mathematics at the interface between graph structures and high dimensional data and geometric analysis.
In the last ten years we have seen an explosion of work in both (a) compressive sensing (sparsity, L1-based methods) and in (b) machine learning
involve graphical structures for large scale and high dimensional data. The focus is on both analysis and algorithm development.
In the case of new algorithms - codes will be tested against state of art machine learning algorithms.
In the case of analytical results - we will draw on expertise in diverse areas of mathematics including differential geometry, nonlinear PDE,
optimization, and spectral analysis of graphs. Application areas represented include machine learning, social network data, modularity optimization,
L1-compressive sensing methods, and image processing.
One area of focus is community detection in large networks.
A current approach for community detection consists in minimizing the so-called modularity functional.
Preliminary experiments using fast compress sensing algorithms shows very promising results for modularity optimization.
A second area of focus is data retrieval, where L1 approaches could lead to significant advances.
Thirdly, graph matching is another problem in which compressed sensing and total variation methods for graphs could have an impact.
Andrea Bertozzi (University of California, Los Angeles)
Research Cluster: Graphs with incomplete information (Feb 17 - March 14, 2014)
Claire Mathieu (École Normale Supérieure)
How can we handle graph problems when the graph is only known imperfectly?
In one setting, the input is a noisy version of some unknown ground truth graph, to which random edges have been added,
destroying the structure : planarity, clustering, distances for example. In another setting, the graph itself can only be
accessed via queries such as shortest path queries, distance queries, or cut queries, and must be inferred from the result
to well-chosen queries ; this comes up in internet tomography. In a third setting, the graph evolves dynamically over time
and solutions must adapt to edge additions and removals.
The cluster will gather researchers around a bi-weekly working group drawing on the skills of the participants in
random graphs and discrete probability, optimization and linear, semi-definite or convex programming methods, structural
graph properties, and randomized dynamic data structures.
Mihai Cucuringu (University of California, Los Angeles)
Research Cluster: Towards Efficient Algorithms Exploiting Graph Structure (April 24 - May 2, 2014)
Blair D. Sullivan (North Carolina State University)
Erik D. Demaine (Massachusetts Institute of Technology)
Daniel Marx (Hungarian Academy of Sciences)
This working group will develop new theoretically grounded approaches to practical problems on graphs and networks using the arsenal of graph structure theory and algorithms
(treewidth, minors, fixed-parameter tractability, approximation algorithms, etc.).
Our approach is to combine the expertise of a mix of junior and senior researchers from three disciplines:
mathematics (graph theory), computer science (fixed-parameter and approximation algorithms), and applied network analysis (social networks, power grid, bioinformatics, etc.).
During this research cluster, we will identify specific practically motivated problems, and tackle the key associated mathematical challenges, with a goal of ultimately
encouraging broader adoption of graph-structure-based tools in the computational community. This goal is particularly important given the emergence of vast quantities of
relational data (a.k.a. networks) and increased need for analysis via scalable algorithms.
We face several challenges in making graph structure techniques applicable to real-world network analysis. First, many of the algorithms currently involve incredibly large constants
(e.g., in their dependence on an excluded minor), so a natural goal is to improve or replace the relevant components with more reasonable dependencies.
Second, we do not know which real-world networks fall into one or more of the mathematical graph classes where structural techniques are applicable.
This problem can be tackled mathematically, through generative models, or experimentally, raising several questions about how to test whether
specific graphs belong to parametrically defined classes. This problem becomes even more interesting when one considers that real-world networks are generally noisy,
which means that the observed graph may have extra edges that place it outside the desired class, even if the intrinsic network satisfies the necessary conditions.
For graphs that are "nearly" within a tractable graph class, can we detect which parts need modification to apply the efficient algorithms, and bound the effect of these
modifications on the computed solution? We are excited by the new theoretical challenges raised by these practical questions, as well as the potential for significantly
impacting the computability of many quantities of interest on real-world graphs.
Semidefinite Programming and Graph Algorithms (February 10-14, 2014)
Monique Laurent (CWI and Tilburg University, Netherlands)
David Phillips (United States Naval Academy)
David Steurer (Cornell University)
Kilian Weinberger (Washington University, St Louis)
[Image courtesy of Philipp Rostalski]
Semidefinite programming is playing an ever increasing role in many areas of computer science and mathematics,
including complexity theory, approximation algorithms for hard graph problems, discrete
geometry, machine learning, and extremal combinatorics.
This workshop will bring together researchers from these different fields. The goal is to explore connections,
learn and share techniques, and build bridges.
Random graphs, stochastic processes on graphs and algorithms for computations on these structures continue to play a dominant role in algorithmic research and discrete mathematics, with recent applications ranging from web search and recommendation engines to social networks and system biology.
This workshop will be an opportunity for researchers from diverse fields to get together and share problems and techniques for handling and analyzing graphs structures. The connections---mathematical, computational, and practical---that arise between these
seemingly-diverse problems and approaches will be emphasized.
Jonathan Kelner (Massachusetts Institute of Technology)
Yiannis Koutis (University of Puerto Rico)
Gary Miller (Carnegie Mellon University)
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
In this workshop, we will bring researchers together to study and
advance this new emerging frontier in algorithmic graph theory.
The analysis of problems modeled by large graphs is greatly
hampered by a lack of efficient computational tools. The purpose of
the workshop is to explore possibilities for designing appropriate
computational methods that draw on recent advances in numerical
methods and scientific computation. Specifically, the questions of
how to form the matrices representing graph Laplacians, and how to
compute the leading eigenvectors of such matrices will be
addressed. It seems likely that these problems will be amenable to
algorithms based on randomized projections that dramatically reduce
the effective dimensionality of the underlying problems. Such
techniques has recently proven highly effective for the related
problems of how to find approximate lists of nearest neighbors for
clouds of points in high dimensional spaces, and for constructing
approximate low-rank factorizations of large matrices. In both
cases, a key observation is that the problem of distortions of
distances that is inherent to randomized projection techniques can
be overcome by using the randomized projections only as
pre-conditioners; they inform the algorithm of where to look, and
then highly accurate deterministic techniques are used to compute
the actual output. The resulting algorithms scale extra-ordinarily
well on modern parallel and multicore architectures. To
successfully address the enormous problems arising in the analysis
of graphs, it is expected that additional machinery will be needed,
such as the use of multi-resolution data structures, and more
efficient scalable randomized projections.