Andrea Bertozzi
(University of California, Los Angeles)
Jonathan Kelner
(Massachusetts Institute of Technology)
Philip Klein (Brown University)
Claire Mathieu
(CNRS, Ecole Normale Supérieure and Brown University)
David Shmoys (Cornell University)
Eli Upfal (Brown University)
[Image courtesy of Eli Upfal]
Introduction
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.
Network Science and Graph Algorithms Semester Program Opening Welcome
11th Floor Lecture Hall
1:35 - 2:05
Graduate student introductions
Thomas Dickerson, Brown University;
Eli Fox-Epstein, Brown University;
Nathanaël François, Université Paris Diderot;
Nicolas Garcia, Carnegie Mellon University;
Huiyi Hu, University of California, Los Angeles;
Slav Kirov, Carnegie Mellon University;
Ahmad Mahmoody, Brown University;
David Meierfrankenfled, Brown University;
Ekaterina Merkurjev, University of California, Los Angeles;
Scott Roche, Northeastern University;
Christopher White, University of Texas at Austin;
Joseph Woodworth, University of California, Los Angeles
11th Floor Lecture Hall
2:05 - 2:10
5-minute Postdoc introduction
Mihai Cucuringu, University of California, Los Angeles
11th Floor Lecture Hall
2:10 - 2:15
5-minute Postdoc introduction
Kyle Fox, University of Illinois at Urbana-Champaign
11th Floor Lecture Hall
2:15 - 2:20
5-minute Postdoc introduction
Blake Hunter, University of California, Los Angeles
11th Floor Lecture Hall
2:20 - 2:25
5-minute Postdoc introduction
Amanda Redlich, Bowdoin College
11th Floor Lecture Hall
2:30 - 2:35
5-minute Postdoc introduction
Michaela Rombach, University of California, Los Angeles
11th Floor Lecture Hall
2:35 - 2:40
5-minute Postdoc introduction
Charalampos Tsourakakis, Carnegie Mellon University
11th Floor Lecture Hall
2:40 - 2:45
5-minute Postdoc introduction
Grigory Yaroslavtsev, Pennsylvania State University
11th Floor Lecture Hall
2:45 - 2:50
5-minute Postdoc introduction
Dominique Zosso, Universtiy of California, Los Angeles
11th Floor Lecture Hall
2:50 - 3:00
Coffee Break
11th Floor Collaborative Space
3:00 - 5:00
Informal Faculty Introductions
11th Floor Lecture Hall
Tuesday
February 4, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
February 5, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:00 - 5:20
Topics in Advanced Algorithms (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
February 6, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffe Break
11th Floor Collaborative Space
Friday
February 7, 2014
Time
Description
Speaker
Location
Abstracts
Slides
1:00 - 2:15
Theory Seminar
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
February 10, 2014
Time
Description
Speaker
Location
Abstracts
Slides
8:30 - 8:55
Registration: Semidefinite Programming and Graph Algorithms Workshop
11th Floor Collaborative Space
8:55 - 9:00
Welcome
ICERM Director
11th Floor Lecture Hall
9:00 - 9:45
The Moment-LP and Moment-SOS approaches in polynomial optimization
Jean Lasserre, Centre National de la Recherche Scientifique (CNRS)
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
Rounding Sum of Squares Relaxations
Boaz Barak, Microsoft Research
11th Floor Lecture Hall
11:30 - 12:15
TBA
Jonathan Kelner, Massachusetts Institute of Technology
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
Convergence of SDP hierarchies using kernel based methods
Stephanie Wehner, National University of Singapore
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
10th Floor Collaborative Space
4:00 - 4:45
Vertical versus horizontal Poincare inequalities
Assaf Naor, New York University
11th Floor Lecture Hall
5:00 - 6:30
Welcome Reception
11th Floor Collaborative Space
Tuesday
February 11, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Expander flows, Geometric embeddings and Graph Partitioning
Claire Mathieu, Ecole Normale Superieure
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
Towards a Better Approximation of Sparsest Cut?
Sanjeev Arora, Princeton University
11th Floor Lecture Hall
11:30 - 12:15
Going off the grid
Benjamin Recht, University of California, Berkeley
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
On the existence of 0/1 polytopes with high semidefinite extension complexity
Sebastian Pokutta, Georgia Institute of Technology
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
4:00 - 4:45
Semidefinite programming and discrepancy- Recent developments
Nikhil Bansal, Technische Universiteit Eindhoven
11th Floor Lecture Hall
Wednesday
February 12, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
TBA
Michel Goemans, Massachusetts Institute of Technology
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
Semidefinite programming bounds for codes and anticodes in Cayley graphs
Frank Vallentin, Universitat zu Koln
11th Floor Lecture Hall
11:30 - 12:15
Near optimal deterministic volume estimation via M-ellipsoids
Daniel Dadush, New York University
11th Floor Lecture Hall
12:30 - 12:40
Group Photo
11th Floor Lecture Hall
12:40 - 2:30
Break for Lunch
2:30 - 3:15
A Non-Convex Optimization Approach to Network Localization- Polynomial-Time Computability and Rigidity-Theoretic Implications
Anthony Man-Cho So, Chinese University of Hong Kong
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 Break
11th Floor Collaborative Space
4:00 - 4:45
Graph parameters from entangled games and quantum zero-error communication.
Jop Briet, New York University
11th Floor Lecture Hall
7:00 - 8:30
Poster Session and Dessert Reception
11th Floor Lecture Hall and Collaborative Space
Thursday
February 13, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Three-dimensional Structure Determination of Molecules without Crystallization- from Electron Microscopy to Semidefinite Programming
Amit Singer, Princeton University
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
On the power of Symmetric SDP relaxations
Prasad Raghavendra, University of California, Berkeley
11th Floor Lecture Hall
11:30 - 12:15
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
Yuan Zhou, Carnegie Mellon University
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
SDP and eigenvalue bounds for the graph partition problem
Renata Sotirov, Tilburg University, Netherlands
11th Floor Lecture Hall
3:25 - 3:25
Please take a moment to complete the survey that was distributed by email.
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
4:00 - 4:45
TBA
Pablo Parrilo, Massachusetts Institute of Technology
11th Floor Lecture Hall
Friday
February 14, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Faster SDP hierarchy solvers for local rounding algorithms
Ali Kemal Sinop, IAS
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
Latent Variable Graphical Model Selection via Convex Optimization
Venkat Chandrasekaran, California Institute of Technology
11th Floor Lecture Hall
11:30 - 12:15
The Matrix Multiplicative Weights Algorithm- Applications to SDP and Online Matrix Prediction
Satyen Kale, Yahoo!
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
1:00 - 2:15
Theory Seminar -ongoing semester seminar- Improving Christofides' Algorithm for the s-t Path Traveling Salesman Problem
David Shmoys, Cornell University
11th Floor Classroom
2:30 - 3:30
Learning how to rank via forbidden patterns - semirankings and the Erdos-Hajnal Conjecture
Krzysztof Choromanski, Google Inc.
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
February 17, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
February 18, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:30
Professional Development: Ethics 1
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
February 19, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:00 - 5:20
Optimization Algorithms for Planar Graphs (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
February 20, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
February 21, 2014
Time
Description
Speaker
Location
Abstracts
Slides
1:00 - 2:15
Theory Seminar- Beyond Locality-Sensitive Hashing
Ilya Razenshteyn, MIT
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
February 24, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
February 25, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:30
Professional Development: Ethics 2
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
February 26, 2014
Time
Description
Speaker
Location
Abstracts
Slides
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 Break
11th Floor Collaborative Space
4:15 - 5:30
Interlacing Families and Kadison--Singer
Adam Marcus, Crisply LLC and Yale University
11th Floor Lecture Hall
Thursday
February 27, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
February 28, 2014
Time
Description
Speaker
Location
Abstracts
Slides
1:00 - 2:15
Theory Seminar
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
March 3, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
March 4, 2014
Time
Description
Speaker
Location
Abstracts
Slides
2:30 - 3:30
Efficiently inferring community structure in bipartite networks
Daniel Larremore, Harvard School of Public Health
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
March 5, 2014
Time
Description
Speaker
Location
Abstracts
Slides
12:00 - 1:00
Research Lunch
Please bring your own lunch. Cookies will be provided. There will be an informal talk by Hang Zhou about her recent interest in correlation clustering in planar graphs, as well as continued discussion on the research interests and ideas everyone is working on.
11th Floor Collaborative Space
3:00 - 5:20
Optimization Algorithms for Planar Graphs (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
March 6, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
March 7, 2014
Time
Description
Speaker
Location
Abstracts
Slides
1:00 - 2:15
Theory Seminar - The Simple Economics of Approximately Optimal Auctions
Jason Hartline, Northwestern University and Harvard University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
March 10, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:00 - 4:15
Maximum Entropy Summary Trees
Howard Karloff, Yahoo! Inc.
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
March 11, 2014
Time
Description
Speaker
Location
Abstracts
Slides
2:30 - 3:30
Flows in 1-crossing-minor-free graphs
Erin Chambers, St. Louis University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
March 12, 2014
Time
Description
Speaker
Location
Abstracts
Slides
2:45 - 3:00
Long Term Visitor Group Photo
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
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
March 13, 2014
Time
Description
Speaker
Location
Abstracts
Slides
2:30 - 3:30
Weekly ICERM Seminar- Subgraphs in Random Graphs
Amanda Redlich, Bowdoin College
10th Floor Classroom
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
March 14, 2014
Time
Description
Speaker
Location
Abstracts
Slides
1:00 - 2:15
Theory Seminar- Bandits with Knapsacks
Alex Slivkins, Microsoft Research, NYC
10th Floor Classroom
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
March 17, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:50
Registration: Stochastic Graph Models Workshop
11th Floor Lecture Hall and Collaborative Space
9:50 - 10:00
Welcome
ICERM Director
11th Floor Lecture Hall
10:00 - 10:45
Evolutionary Dynamics on Graphs
Leslie Ann Goldberg, University of Oxford
11th Floor Lecture Hall
11:00 - 11:45
Fast Testing of Graph Properties
Artur Czumaj, University of Warwick
11th Floor Lecture Hall
12:00 - 1:45
Break for Lunch
1:45 - 2:30
New Online Algorithms for Story Scheduling in Web Advertising
Susanne Albers, TU Munich
11th Floor Lecture Hall
2:45 - 3:30
Trace Complexity of Network Reconstruction
Flavio Chierichetti, Sapienza University of Rome
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
Distributed Algorithmic Foundations of Dynamic Networks
Gopal Pandurangan, Brown University and NTU, Singapore
11th Floor Lecture Hall
5:00 - 6:30
Welcome Reception
11th Floor Collaborative Space
Tuesday
March 18, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:30 - 10:00
Open for Collaboration (Bagels and fruit provided)
11th Floor Collaborative Space
10:00 - 10:45
Force-Directed Graph Drawing Using Social Gravity and Scaling
Michael Goodrich, University of California, Irvine
11th Floor Lecture Hall
11:00 - 11:45
Algorithms on Evolving Data Sets
Mohammad Mahdian, Google INC
11th Floor Lecture Hall
12:00 - 1:45
Break for Lunch
1:45 - 2:30
Computing Stationary Distribution, Locally
Devavrat Shah, Massachusetts Institute of Technology
11th Floor Lecture Hall
2:45 - 3:30
Reconstructing Latent Similarities in a Multiplex Social Network
Alex Slivkins, Microsoft Research
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
Elite, Periphery and Symmetry in Social Networks- An Axiomatic Approach
Chen Avin, Ben-Gurion University
11th Floor Lecture Hall
Wednesday
March 19, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:30 - 10:00
Open for Collaboration (Bagels and fruit provided)
11th Floor Collaborative Space
10:00 - 10:45
Impromptu Updating in a Distributed Dynamic Network
Valerie King, University of Victoria
11th Floor Lecture Hall
11:00 - 11:45
Peeling Algorithms
Michael Mitzenmacher, Harvard University
11th Floor Lecture Hall
12:00 - 12:15
Group Photo
11th Floor Lecture Hall
12:15 - 1:45
Break for Lunch
1:45 - 2:30
On the Complexity of Information Spreading in Dynamic Networks
Rajmohan Rajaraman, Northeastern University
11th Floor Lecture Hall
2:45 - 3:30
Power Law Complexity
Piotr Sankowski, University of Warsaw
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
Chasing changes in dynamic structures.
Eli Upfal, Brown University
11th Floor Lecture Hall
7:00 - 8:30
Poster Session and Dessert Reception
11th Floor Lecture Hall and Collaborative Space
Thursday
March 20, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:30 - 10:00
Open for Collaboration (Bagels and fruit provided)
11th Floor Collaborative Space
10:00 - 10:45
The Power of Two Choices in Distributed Voting
Robert Elsaesser, Universität Salzburg
11th Floor Lecture Hall
11:00 - 11:45
Efficient computation of the weighted clustering coefficient
Stefano Leonardi, Sapienza University of Rome
11th Floor Lecture Hall
12:00 - 1:45
Break for Lunch
1:45 - 2:30
Improved bounds and algorithms for graph cuts and network reliability
Aravind Srinivasan, University of Maryland
11th Floor Lecture Hall
2:45 - 3:30
Online Stochastic Matching- New Results and Open Problems
Vahab Mirrokni, Google Inc.
11th Floor Lecture Hall
3:30 - 3:35
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
Similarity Ranking in Large-Scale Bipartite Graphs
Alessandro Epasto, Universita di Roma La Sapienza
11th Floor Lecture Hall
Friday
March 21, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:30 - 10:00
Open for Collaboration (Bagels and fruit provided)
11th Floor Collaborative Space
10:00 - 10:45
Randomly coloring random graphs
Alan Frieze, Carnegie Mellon University
11th Floor Lecture Hall
11:00 - 11:45
Estimating Network Parameters
Ravi Kumar, Google Inc.
11th Floor Lecture Hall
12:00 - 1:30
Break for Lunch
1:30 - 2:30
Theory Seminar (ongoing semester seminar)- Improved Approximations for Graph-TSP in Regular Graphs
R. Ravi, Carnegie Mellon University
11th Floor Lecture Hall
2:45 - 3:30
An Efficient reconciliation algorithm for social networks
Silvio Lattanzi, Google Inc.
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
On the Glass Ceiling Effect in Social Networks
Zvi Lotker, Ben-Gurion University of the Negev and Claire Mathieu, Brown University
11th Floor Lecture Hall
Monday
March 24, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
March 25, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
March 26, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:00 - 5:20
Optimization Algorithms for Planar Graphs (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
March 27, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
March 28, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
March 31, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
April 1, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
April 2, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:00 - 5:20
Optimization Algorithms for Planar Graphs (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
April 3, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
April 4, 2014
Time
Description
Speaker
Location
Abstracts
Slides
1:00 - 2:00
Theory Seminar-Superlinear Lower Bounds for Multipass Graph Processing
Venkatesan Guruswami, Carnegie-Mellon University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
April 7, 2014
Time
Description
Speaker
Location
Abstracts
Slides
8:30 - 8:55
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
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
Open Problems for Real Data
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
TBA
TBA
11th Floor Lecture Hall
Monday
April 14, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
April 15, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
April 16, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:00 - 5:20
Optimization Algorithms for Planar Graphs (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
April 17, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
April 18, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:30
Coffee/Tea Break
11th Floor Collaborative Space
9:30 - 10:15
Local computation algorithms for sparse graphs
Ronitt Rubinfeld, Massachusetts Institute of Technology
11th Floor Lecture Hall
10:30 - 10:55
Approximating matching size from random streams
Michael Kapralov, Massachusetts Institute of Technology
11th Floor Lecture Hall
11:00 - 11:25
Turnstile Streaming Algorithms Might as Well Be Linear Sketches
Huy Le Nguyen, Princeton University
11th Floor Lecture Hall
1:00 - 1:45
Testing and Reconstruction of Lipschitz Functions
Sofya Raskhodnikova, Pennsylvania State University and Boston University
11th Floor Lecture Hall
2:00 - 2:45
Analyzing Big Graphs via Sketching and Streaming
Andrew McGregor, University of Massachusetts, Amherst
11th Floor Lecture Hall
3:00 - 3:45
Streaming Interactive Proofs or: How I Learned to Stop Worrying and Trust the Cloud
Amit Chakrabarti, Dartmouth College
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
April 21, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
April 22, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
April 23, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:00 - 5:20
Optimization Algorithms for Planar Graphs (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
April 24, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
April 25, 2014
Time
Description
Speaker
Location
Abstracts
Slides
1:00 - 2:00
Storage and Search in Dynamic Peer-to-Peer Networks
John Augustine, IIT Madras
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
April 28, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Tuesday
April 29, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Wednesday
April 30, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:00 - 5:20
Optimization Algorithms for Planar Graphs (ongoing semester course)
Phil Klein, Brown University and Claire Mathieu, Brown University
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Thursday
May 1, 2014
Time
Description
Speaker
Location
Abstracts
Slides
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Friday
May 2, 2014
Time
Description
Speaker
Location
Abstracts
Slides
1:00 - 2:15
New Algorithms for Representation Learning and Beyond
Ankur Moitra, MIT
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Monday
May 5, 2014
Time
Description
Speaker
Location
Abstracts
Slides
8:30 - 8:55
Registration
11th Floor Collaborative Space
8:55 - 9:00
Welcome
ICERM Director
11th Floor Lecture Hall
9:00 - 9:45
Eigenvectors, Heat Kernels, and Low Dimensional Representation of Data Sets
Peter Jones, Yale University
11th Floor Lecture Hall
9:50 - 10:35
Multiscale Geometric Methods for Statistical Learning and Data in High-Dimensiona
Mauro Maggioni, Duke University
11th Floor Lecture Hall
10:40 - 11:10
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Tracking Influences within Dynamic Networks
Rebecca Willett, University of Wisconsin
11th Floor Lecture Hall
12:00 - 2:00
Lunch Break and Free Time
2:00 - 2:45
Robust and Fast Subspace Recovery
Gilad Lerman, University of Minnesota
11th Floor Lecture Hall
2:50 - 3:35
TBA
Roy Lederman, Yale University
11th Floor Lecture Hall
3:40 - 4:10
Coffee Break
11th Floor Collaborative Space
4:10 - 4:55
Diffuse Scattering on Graphs and Combinatorial Inverse Problems
Anna Gilbert, University of Michigan
11th Floor Lecture Hall
5:00 - 6:30
Welcome Reception
11th Floor Collaborative Space
Tuesday
May 6, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Covariance Matrix Estimation for the Cryo-EM Heterogeneity Problem
Amit Singer, Princeton University
11th Floor Lecture Hall
9:50 - 10:35
A randomized approximate nearest neighbors algorithm
Andrei Osipov, Yale University
11th Floor Lecture Hall
10:40 - 11:10
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Eigenvector localization, implicit regularization, and algorithmic anti-differentiation for large-scale graphs and networked data
Michael W. Mahoney, University of California, Berkeley
11th Floor Lecture Hall
12:00 - 2:00
Lunch Break and Free Time
2:00 - 2:45
TBA
Vladimir Rokhlin, Yale University
11th Floor Lecture Hall
2:50 - 3:35
Gaps in eigenfunctions of Graphs
Fan Chung, University of California, San Diego
11th Floor Lecture Hall
3:40 - 4:10
Coffee Break
11th Floor Collaborative Space
4:10 - 4:55
Inverse problems on random graphs and censored block models
Emmanuel Abbe, Princeton University
11th Floor Lecture Hall
Wednesday
May 7, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
New Algorithms for Learning Incoherent and Overcomplete Dictionaries
Rong Ge, Microsoft Research
11th Floor Lecture Hall
9:50 - 10:35
A threshold for reconstruction in stochastic block models
Joe Neeman, University of Texas at Austin
11th Floor Lecture Hall
10:40 - 11:10
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Network Clustering, the Block Stochastic Model, and a Regular Graph
Ioana Dumitriu, University of Washington
11th Floor Lecture Hall
12:00 - 12:05
Group Photo
11th Floor Lecture Hall
12:05 - 2:00
Lunch Break and Free Time
2:00 - 2:45
Dimension reduction in the l1 norm- When and how is it possible
Rachel Ward, University of Texas at Austin
11th Floor Lecture Hall
2:50 - 3:35
Random weighted projections, random quadratic forms and random eigenvectors
Ke Wang, University of Minnesota
11th Floor Lecture Hall
3:40 - 4:10
Coffee Break
11th Floor Collaborative Space
4:10 - 4:55
Spectral algorithms for graph mining and analysis
Yiannis Koutis, University of Puerto Rico
11th Floor Lecture Hall
7:00 - 8:30
Poster Session and Dessert Reception
11th Floor Collaborative Space
Thursday
May 8, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Information-theoretic learned linear projections for dimensionality reduction
Lawrence Carin, Duke University
11th Floor Lecture Hall
9:50 - 10:35
A Polynomial Time Algorithm for Lossy Population Recovery
Ankur Moitra, Massachusetts Institute of Technology
11th Floor Lecture Hall
10:40 - 11:10
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Permanent estimators via random matrices
Mark Rudelson, Univeristy of Michigan
11th Floor Lecture Hall
12:00 - 2:00
Lunch Break and Free Time
2:00 - 2:45
A simple spectral algorithm for a general clustering problem
Van Vu, Yale University
11th Floor Lecture Hall
2:50 - 3:35
Random perturbation of low rank matrices- Improving classical bounds
Sean O'Rourke, Yale University
11th Floor Lecture Hall
3:40 - 4:10
Coffee Break
11th Floor Collaborative Space
4:10 - 4:55
Is Belief Propagation a Spectral algorithm
Elchanan Mossel, University of California, Berkeley
11th Floor Lecture Hall
Friday
May 9, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:50 - 10:35
Panel Summary
Panel Discussion Chair: Anna Gilbert, University of Michigan
11th Floor Lecture Hall
10:30 - 11:00
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Panel Summary
11th Floor Lecture Hall
12:00 - 5:00
Afternoon Free for Collaborations
Tuesday
February 4, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:15 - 9:30
Welcome
11th Floor Lecture Hall
9:30 - 10:30
The geometry of unweighted k-nearest neighbor graphs- first results and many questions
Ulrike von Luxbourg, Universitat Hamburg
11th Floor Lecture Hall
10:30 - 11:30
From partial differential equations to graphs- curvature and clusters
Semidefinite Programming and Graph Algorithms (February 10-14, 2014)
Organizing Committee
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]
Description
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.
Registration: Semidefinite Programming and Graph Algorithms Workshop
11th Floor Collaborative Space
8:55 - 9:00
Welcome
ICERM Director
11th Floor Lecture Hall
9:00 - 9:45
The Moment-LP and Moment-SOS approaches in polynomial optimization
Jean Lasserre, Centre National de la Recherche Scientifique (CNRS)
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
Rounding Sum of Squares Relaxations
Boaz Barak, Microsoft Research
11th Floor Lecture Hall
11:30 - 12:15
TBA
Jonathan Kelner, Massachusetts Institute of Technology
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
Convergence of SDP hierarchies using kernel based methods
Stephanie Wehner, National University of Singapore
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
10th Floor Collaborative Space
4:00 - 4:45
Vertical versus horizontal Poincare inequalities
Assaf Naor, New York University
11th Floor Lecture Hall
5:00 - 6:30
Welcome Reception
11th Floor Collaborative Space
Tuesday
February 11, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Expander flows, Geometric embeddings and Graph Partitioning
Claire Mathieu, Ecole Normale Superieure
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
Towards a Better Approximation of Sparsest Cut?
Sanjeev Arora, Princeton University
11th Floor Lecture Hall
11:30 - 12:15
Going off the grid
Benjamin Recht, University of California, Berkeley
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
On the existence of 0/1 polytopes with high semidefinite extension complexity
Sebastian Pokutta, Georgia Institute of Technology
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
4:00 - 4:45
Semidefinite programming and discrepancy- Recent developments
Nikhil Bansal, Technische Universiteit Eindhoven
11th Floor Lecture Hall
Wednesday
February 12, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
TBA
Michel Goemans, Massachusetts Institute of Technology
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
Semidefinite programming bounds for codes and anticodes in Cayley graphs
Frank Vallentin, Universitat zu Koln
11th Floor Lecture Hall
11:30 - 12:15
Near optimal deterministic volume estimation via M-ellipsoids
Daniel Dadush, New York University
11th Floor Lecture Hall
12:30 - 12:40
Group Photo
11th Floor Lecture Hall
12:40 - 2:30
Break for Lunch
2:30 - 3:15
A Non-Convex Optimization Approach to Network Localization- Polynomial-Time Computability and Rigidity-Theoretic Implications
Anthony Man-Cho So, Chinese University of Hong Kong
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 Break
11th Floor Collaborative Space
4:00 - 4:45
Graph parameters from entangled games and quantum zero-error communication.
Jop Briet, New York University
11th Floor Lecture Hall
7:00 - 8:30
Poster Session and Dessert Reception
11th Floor Lecture Hall and Collaborative Space
Thursday
February 13, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Three-dimensional Structure Determination of Molecules without Crystallization- from Electron Microscopy to Semidefinite Programming
Amit Singer, Princeton University
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
On the power of Symmetric SDP relaxations
Prasad Raghavendra, University of California, Berkeley
11th Floor Lecture Hall
11:30 - 12:15
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
Yuan Zhou, Carnegie Mellon University
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
SDP and eigenvalue bounds for the graph partition problem
Renata Sotirov, Tilburg University, Netherlands
11th Floor Lecture Hall
3:25 - 3:25
Please take a moment to complete the survey that was distributed by email.
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
4:00 - 4:45
TBA
Pablo Parrilo, Massachusetts Institute of Technology
11th Floor Lecture Hall
Friday
February 14, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Faster SDP hierarchy solvers for local rounding algorithms
Ali Kemal Sinop, IAS
11th Floor Lecture Hall
10:00 - 10:30
Coffee Break
11th Floor Collaborative Space
10:30 - 11:15
Latent Variable Graphical Model Selection via Convex Optimization
Venkat Chandrasekaran, California Institute of Technology
11th Floor Lecture Hall
11:30 - 12:15
The Matrix Multiplicative Weights Algorithm- Applications to SDP and Online Matrix Prediction
Satyen Kale, Yahoo!
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
1:00 - 2:15
Theory Seminar -ongoing semester seminar- Improving Christofides' Algorithm for the s-t Path Traveling Salesman Problem
David Shmoys, Cornell University
11th Floor Classroom
2:30 - 3:30
Learning how to rank via forbidden patterns - semirankings and the Erdos-Hajnal Conjecture
Krzysztof Choromanski, Google Inc.
11th Floor Lecture Hall
3:30 - 4:00
Coffee Break
11th Floor Collaborative Space
Stochastic Graph Models (March 17-21, 2014)
Organizing Committee
Susanne Albers
(Humboldt-Universitat, Berlin)
Ravi Kumar
(Google)
Michael Mitzenmacher (Harvard University)
Eli Upfal (Brown University)
Description
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.
New Online Algorithms for Story Scheduling in Web Advertising
Susanne Albers, TU Munich
11th Floor Lecture Hall
2:45 - 3:30
Trace Complexity of Network Reconstruction
Flavio Chierichetti, Sapienza University of Rome
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
Distributed Algorithmic Foundations of Dynamic Networks
Gopal Pandurangan, Brown University and NTU, Singapore
11th Floor Lecture Hall
5:00 - 6:30
Welcome Reception
11th Floor Collaborative Space
Tuesday
March 18, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:30 - 10:00
Open for Collaboration (Bagels and fruit provided)
11th Floor Collaborative Space
10:00 - 10:45
Force-Directed Graph Drawing Using Social Gravity and Scaling
Michael Goodrich, University of California, Irvine
11th Floor Lecture Hall
11:00 - 11:45
Algorithms on Evolving Data Sets
Mohammad Mahdian, Google INC
11th Floor Lecture Hall
12:00 - 1:45
Break for Lunch
1:45 - 2:30
Computing Stationary Distribution, Locally
Devavrat Shah, Massachusetts Institute of Technology
11th Floor Lecture Hall
2:45 - 3:30
Reconstructing Latent Similarities in a Multiplex Social Network
Alex Slivkins, Microsoft Research
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
Elite, Periphery and Symmetry in Social Networks- An Axiomatic Approach
Chen Avin, Ben-Gurion University
11th Floor Lecture Hall
Wednesday
March 19, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:30 - 10:00
Open for Collaboration (Bagels and fruit provided)
11th Floor Collaborative Space
10:00 - 10:45
Impromptu Updating in a Distributed Dynamic Network
Valerie King, University of Victoria
11th Floor Lecture Hall
11:00 - 11:45
Peeling Algorithms
Michael Mitzenmacher, Harvard University
11th Floor Lecture Hall
12:00 - 12:15
Group Photo
11th Floor Lecture Hall
12:15 - 1:45
Break for Lunch
1:45 - 2:30
On the Complexity of Information Spreading in Dynamic Networks
Rajmohan Rajaraman, Northeastern University
11th Floor Lecture Hall
2:45 - 3:30
Power Law Complexity
Piotr Sankowski, University of Warsaw
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
Chasing changes in dynamic structures.
Eli Upfal, Brown University
11th Floor Lecture Hall
7:00 - 8:30
Poster Session and Dessert Reception
11th Floor Lecture Hall and Collaborative Space
Thursday
March 20, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:30 - 10:00
Open for Collaboration (Bagels and fruit provided)
11th Floor Collaborative Space
10:00 - 10:45
The Power of Two Choices in Distributed Voting
Robert Elsaesser, Universität Salzburg
11th Floor Lecture Hall
11:00 - 11:45
Efficient computation of the weighted clustering coefficient
Stefano Leonardi, Sapienza University of Rome
11th Floor Lecture Hall
12:00 - 1:45
Break for Lunch
1:45 - 2:30
Improved bounds and algorithms for graph cuts and network reliability
Aravind Srinivasan, University of Maryland
11th Floor Lecture Hall
2:45 - 3:30
Online Stochastic Matching- New Results and Open Problems
Vahab Mirrokni, Google Inc.
11th Floor Lecture Hall
3:30 - 3:35
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
Similarity Ranking in Large-Scale Bipartite Graphs
Alessandro Epasto, Universita di Roma La Sapienza
11th Floor Lecture Hall
Friday
March 21, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:30 - 10:00
Open for Collaboration (Bagels and fruit provided)
11th Floor Collaborative Space
10:00 - 10:45
Randomly coloring random graphs
Alan Frieze, Carnegie Mellon University
11th Floor Lecture Hall
11:00 - 11:45
Estimating Network Parameters
Ravi Kumar, Google Inc.
11th Floor Lecture Hall
12:00 - 1:30
Break for Lunch
1:30 - 2:30
Theory Seminar (ongoing semester seminar)- Improved Approximations for Graph-TSP in Regular Graphs
R. Ravi, Carnegie Mellon University
11th Floor Lecture Hall
2:45 - 3:30
An Efficient reconciliation algorithm for social networks
Silvio Lattanzi, Google Inc.
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
On the Glass Ceiling Effect in Social Networks
Zvi Lotker, Ben-Gurion University of the Negev and Claire Mathieu, Brown University
11th Floor Lecture Hall
Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond (April 7-11, 2014)
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.
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
11th Floor Lecture Hall
12:30 - 2:30
Break for Lunch
2:30 - 3:15
Open Problems for Real Data
11th Floor Lecture Hall
3:30 - 4:00
Coffee/Tea Break
11th Floor Collaborative Space
4:00 - 4:45
TBA
TBA
11th Floor Lecture Hall
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 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.
Eigenvectors, Heat Kernels, and Low Dimensional Representation of Data Sets
Peter Jones, Yale University
11th Floor Lecture Hall
9:50 - 10:35
Multiscale Geometric Methods for Statistical Learning and Data in High-Dimensiona
Mauro Maggioni, Duke University
11th Floor Lecture Hall
10:40 - 11:10
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Tracking Influences within Dynamic Networks
Rebecca Willett, University of Wisconsin
11th Floor Lecture Hall
12:00 - 2:00
Lunch Break and Free Time
2:00 - 2:45
Robust and Fast Subspace Recovery
Gilad Lerman, University of Minnesota
11th Floor Lecture Hall
2:50 - 3:35
TBA
Roy Lederman, Yale University
11th Floor Lecture Hall
3:40 - 4:10
Coffee Break
11th Floor Collaborative Space
4:10 - 4:55
Diffuse Scattering on Graphs and Combinatorial Inverse Problems
Anna Gilbert, University of Michigan
11th Floor Lecture Hall
5:00 - 6:30
Welcome Reception
11th Floor Collaborative Space
Tuesday
May 6, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Covariance Matrix Estimation for the Cryo-EM Heterogeneity Problem
Amit Singer, Princeton University
11th Floor Lecture Hall
9:50 - 10:35
A randomized approximate nearest neighbors algorithm
Andrei Osipov, Yale University
11th Floor Lecture Hall
10:40 - 11:10
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Eigenvector localization, implicit regularization, and algorithmic anti-differentiation for large-scale graphs and networked data
Michael W. Mahoney, University of California, Berkeley
11th Floor Lecture Hall
12:00 - 2:00
Lunch Break and Free Time
2:00 - 2:45
TBA
Vladimir Rokhlin, Yale University
11th Floor Lecture Hall
2:50 - 3:35
Gaps in eigenfunctions of Graphs
Fan Chung, University of California, San Diego
11th Floor Lecture Hall
3:40 - 4:10
Coffee Break
11th Floor Collaborative Space
4:10 - 4:55
Inverse problems on random graphs and censored block models
Emmanuel Abbe, Princeton University
11th Floor Lecture Hall
Wednesday
May 7, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
New Algorithms for Learning Incoherent and Overcomplete Dictionaries
Rong Ge, Microsoft Research
11th Floor Lecture Hall
9:50 - 10:35
A threshold for reconstruction in stochastic block models
Joe Neeman, University of Texas at Austin
11th Floor Lecture Hall
10:40 - 11:10
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Network Clustering, the Block Stochastic Model, and a Regular Graph
Ioana Dumitriu, University of Washington
11th Floor Lecture Hall
12:00 - 12:05
Group Photo
11th Floor Lecture Hall
12:05 - 2:00
Lunch Break and Free Time
2:00 - 2:45
Dimension reduction in the l1 norm- When and how is it possible
Rachel Ward, University of Texas at Austin
11th Floor Lecture Hall
2:50 - 3:35
Random weighted projections, random quadratic forms and random eigenvectors
Ke Wang, University of Minnesota
11th Floor Lecture Hall
3:40 - 4:10
Coffee Break
11th Floor Collaborative Space
4:10 - 4:55
Spectral algorithms for graph mining and analysis
Yiannis Koutis, University of Puerto Rico
11th Floor Lecture Hall
7:00 - 8:30
Poster Session and Dessert Reception
11th Floor Collaborative Space
Thursday
May 8, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:00 - 9:45
Information-theoretic learned linear projections for dimensionality reduction
Lawrence Carin, Duke University
11th Floor Lecture Hall
9:50 - 10:35
A Polynomial Time Algorithm for Lossy Population Recovery
Ankur Moitra, Massachusetts Institute of Technology
11th Floor Lecture Hall
10:40 - 11:10
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Permanent estimators via random matrices
Mark Rudelson, Univeristy of Michigan
11th Floor Lecture Hall
12:00 - 2:00
Lunch Break and Free Time
2:00 - 2:45
A simple spectral algorithm for a general clustering problem
Van Vu, Yale University
11th Floor Lecture Hall
2:50 - 3:35
Random perturbation of low rank matrices- Improving classical bounds
Sean O'Rourke, Yale University
11th Floor Lecture Hall
3:40 - 4:10
Coffee Break
11th Floor Collaborative Space
4:10 - 4:55
Is Belief Propagation a Spectral algorithm
Elchanan Mossel, University of California, Berkeley
11th Floor Lecture Hall
Friday
May 9, 2014
Time
Description
Speaker
Location
Abstracts
Slides
9:50 - 10:35
Panel Summary
Panel Discussion Chair: Anna Gilbert, University of Michigan
11th Floor Lecture Hall
10:30 - 11:00
Coffee/Tea Break
11th Floor Collaborative Space
11:10 - 11:55
Panel Summary
11th Floor Lecture Hall
12:00 - 5:00
Afternoon Free for Collaborations
Spring 2014 Research Clusters
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)
Organizer:
Andrea Bertozzi (University of California, Los Angeles)
Thomas Laurent (Loyola Marymount University)
Description
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)
Organizer:
Claire Mathieu (École Normale Supérieure)
Description
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)
Organizers:
Blair D. Sullivan (North Carolina State University)
Erik D. Demaine (Massachusetts Institute of Technology)
Daniel Marx (Hungarian Academy of Sciences)
Description
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.