Research Cluster: Graphs with incomplete information
Feb 17  Mar 15, 2014
Organizing Committee
 Claire Mathieu
Ecole Normale Suptrieure
Abstract
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 wellchosen 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 biweekly working group drawing on the skills of the participants in random graphs and discrete probability, optimization and linear, semidefinite or convex programming methods, structural graph properties, and randomized dynamic data structures.
Confirmed Speakers & Participants
Talks will be presented virtually or inperson as indicated in the schedule below.
 Speaker
 Poster Presenter
 Attendee
 Virtual Attendee

Mihai Cucuringu
University of California, Los Angeles

Nathanaël François
Universite de Paris VII (Denis Diderot)

Howard Karloff
Yahoo! Inc.

Claire Mathieu
Ecole Normale Suptrieure

Hang Zhou
Ecole Normale Suptrieure
Associated Semester Workshops
Network Science and Graph Algorithms
Feb 3  May 9, 2014
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.
Organizing Committee
 Andrea Bertozzi
 Jonathan Kelner
 Philip Klein
 Claire Mathieu
 David Shmoys
 Eli Upfal
Research Cluster: Geometric analysis methods for graph algorithms
Feb 3  28, 2014
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, L1based 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, L1compressive 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... (more)
Organizing Committee
 Andrea Bertozzi
 Thomas Laurent
Semidefinite Programming and Graph Algorithms
Feb 10  14, 2014
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.
Organizing Committee
 Monique Laurent
 David Phillips
 David Steurer
 Kilian Weinberger
Stochastic Graph Models
Mar 17  21, 2014
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 connectionsmathematical, computational, and practicalthat arise between these seeminglydiverse problems and approaches will be emphasized.
Organizing Committee
 Susanne Albers
 Ravi Kumar
 Michael Mitzenmacher
 Eli Upfal
Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond
Apr 7  11, 2014
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 spectrumparticularly 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 linearalgebraic properties of the matrices we associate to graphs.
A particularly fruitful example of this... (more)
Organizing Committee
 Jonathan Kelner
 Ioannis Koutis
 Gary Miller
Research Cluster: Towards Efficient Algorithms Exploiting Graph Structure
Apr 24  May 3, 2014
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, fixedparameter 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 (fixedparameter 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 graphstructurebased 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... (more)
Organizing Committee
 Erik Demaine
 Daniel Marx
 Blair Sullivan
Eigenvectors in graph theory and related problems in numerical linear algebra
May 5  9, 2014
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 lowrank factorizations of large matrices. In both cases, a key observation is that the problem of distortions of distances that is inherent to... (more)
Organizing Committee
 Anna Gilbert
 Peter Jones
 Gunnar Martinsson
 Van Vu
Research Clusters
Research Cluster: Geometric analysis methods for graph algorithms
Feb 3  28, 2014
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, L1based 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, L1compressive 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... (more)
Organizing Committee
 Andrea Bertozzi
 Thomas Laurent
Research Cluster: Graphs with incomplete information
Feb 17  Mar 15, 2014
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 wellchosen 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 biweekly working group drawing on the skills of the participants in random graphs and discrete probability, optimization and linear, semidefinite or convex programming methods, structural graph properties, and randomized dynamic data structures.
Organizing Committee
 Claire Mathieu
Research Cluster: Towards Efficient Algorithms Exploiting Graph Structure
Apr 24  May 3, 2014
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, fixedparameter 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 (fixedparameter 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 graphstructurebased 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... (more)
Organizing Committee
 Erik Demaine
 Daniel Marx
 Blair Sullivan