ICERM Semester Program on "Network Science and Graph Algorithms"
(February 3, 2014  May 9, 2014)
 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)
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.
Associated Events & Information
Spring 2014 Semester Workshops
Dates  Title  Organizers 

February 1014, 2014  Semidefinite Programming and Graph Algorithms  Monique Laurent, David Phillips, David Steurer, Kilian Weinberger 
March 1721, 2014  Stochastic Graph Models  Eli Upfal, Susanne Albers, Ravi Kumar, Michael Mitzenmacher 
April 711, 2014  Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond  Jonathan Kelner, Yiannis Koutis, Gary Miller 
May 5  9, 2014  Eigenvectors in graph theory and related problems in numerical linear algebra  Anna Gilbert, Peter Jones, Gunnar Martinsson, Van Vu 
This page will show upcoming seminars that will be scheduled by organizers, speakers, and participants of the Spring 2014 semester program. Walkins are welcomed and encouraged for these seminars. Please check back regularly for updates.
We provide an iCal link for those attendees who wish to sync their own devices and/or calendars to our schedule.
Monday  February 3, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
1:30  1:35  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 FoxEpstein, 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  5minute Postdoc introduction  Mihai Cucuringu, University of California, Los Angeles  11th Floor Lecture Hall  
2:10  2:15  5minute Postdoc introduction  Kyle Fox, University of Illinois at UrbanaChampaign  11th Floor Lecture Hall  
2:15  2:20  5minute Postdoc introduction  Blake Hunter, University of California, Los Angeles  11th Floor Lecture Hall  
2:20  2:25  5minute Postdoc introduction  Amanda Redlich, Bowdoin College  11th Floor Lecture Hall  
2:30  2:35  5minute Postdoc introduction  Michaela Rombach, University of California, Los Angeles  11th Floor Lecture Hall  
2:35  2:40  5minute Postdoc introduction  Charalampos Tsourakakis, Carnegie Mellon University  11th Floor Lecture Hall  
2:40  2:45  5minute Postdoc introduction  Grigory Yaroslavtsev, Pennsylvania State University  11th Floor Lecture Hall  
2:45  2:50  5minute 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 MomentLP and MomentSOS 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 Mellipsoids  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 NonConvex Optimization Approach to Network Localization PolynomialTime Computability and RigidityTheoretic Implications  Anthony ManCho 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 zeroerror 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  Threedimensional 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 st 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 ErdosHajnal 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 LocalitySensitive 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 KadisonSinger  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 1crossingminorfree 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 
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  ForceDirected 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, BenGurion 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 LargeScale 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 GraphTSP 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, BenGurion 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 SeminarSuperlinear Lower Bounds for Multipass Graph Processing  Venkatesan Guruswami, CarnegieMellon 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 UrbanaChampaign  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 NearlyLinearTime 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 Rank1 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  
7:00  8:30  Poster Session and Dessert Reception  11th Floor Collaborative Space and 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  Antidifferentiating approximation alogrithms for mincuts 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 higherorder 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 OveisGharan, 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  Largescale Computations of EdgeImportance 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 PeertoPeer 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 HighDimensiona  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 CryoEM 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 antidifferentiation for largescale 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  Informationtheoretic 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 knearest 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  Yves van Gennip, University of Nottingham  11th Floor Lecture Hall  
11:30  1:00  Break for Lunch  
1:00  1:30  Distance geometry on graphs via synchronization  Mihai Cucuringu, UCLA  11th Floor Lecture Hall  
1:30  2:00  TBA  Michaela Puck Rombach, UCLA  11th Floor Lecture Hall  
2:00  2:15  Break  11th Floor Collaborative Space  
2:15  3:15  Applied Harmonic Analysis meets Compressed Sensing  Gitta Kutyniok, TU Berlin  11th Floor Lecture Hall  
4:45  5:45  Poster Session  11th Floor Collaborative Space 
Wednesday  February 5, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
10:00  11:00  Scalable Gaussian process models on matrices and tensors  Yuan Qi, Purdue University  11th Floor Lecture Hall  
11:00  11:30  Break  11th Floor Collaborative Space  
11:30  12:00  Spectral Methods for Analyzing Large Data  Blake Hunter, UCLA  11th Floor Lecture Hall  
12:00  12:30  Minimal Dirichlet energy partitions for graphs  Chris White, University of Texas at Austin  11th Floor Lecture Hall 
Thursday  February 6, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
10:00  11:00  Proximal splitting algorithms for two class and multiclass total variation clustering  Thomas Laurent, Loyola Marymount University  11th Floor Lecture Hall  
11:00  12:00  Pooling fidelity and phase recovery  Arthur Szlam, City College, CUNY  11th Floor Lecture Hall 
Friday  February 7, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:00  Random Graph Models for Image Patches  Francois Meyer, University of Colorado at Boulder  11th Floor Lecture Hall  
11:00  11:30  Break  11th Floor Collaborative Space  
11:30  12:00  Nonlocal Beltrami and Beltrami on graph  Dominique Zosso, UCLA  11th Floor Lecture Hall  
1:30  2:30  Graph cut, convex relaxation and continuous maxflow problems  Tai XueCheng, University of Bergen  10th Floor Classroom 
Thursday  April 24, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
8:30  9:00  Registration  11th Floor Collaborative Space  
9:00  10:20  Basic techniques of fixedparameter tractability (Part 1)  Saket Saurabh, Institute of Mathematical Sciences  11th Floor Lecture Hall  
10:30  11:00  Coffee/Tea Break  11th Floor Collaborative Space  
11:00  12:30  Basic techniques of fixedparameter tractability (Part 2)  Daniel Lokshtanov, University of Bergen  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Kernelization  Saket Saurabh, Institute of Mathematical Sciences  11th Floor Lecture Hall  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research 
Friday  April 25, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:20  Treewidth and applications  Fedor Fomin, University of Bergen  11th Floor Lecture Hall  
10:30  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  11:15  Open Problem Session  11th Floor Lecture Hall  
11:15  12:45  Minors and Algorithms  Erik Demaine, Massachusetts Institute of Technology  11th Floor Lecture Hall  
12:45  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research 
Saturday  April 26, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:20  Approximation Algorithms  Mohammad Taghi Hajiaghayi, University of Maryland  11th Floor Lecture Hall  
10:30  11:00  Coffee/Tea Break  11th Floor Collaborative Space  
11:00  12:30  Lower bounds  Daniel Marx, Hungarian Academy of Sciences (MTA)  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research 
Sunday  April 27, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:20  Separators  Daniel Marx, Hungarian Academy of Sciences (MTA)  11th Floor Lecture Hall  
10:30  11:00  Coffee/Tea Break  
11:00  12:30  Connecting to the RealWorld Applications  Blair Sullivan, North Carolina State University  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  
4:00  5:00  Research 
Monday  April 28, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Opening Session  11th Floor Lecture Hall  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research  
5:00  5:30  Problem Session Update  11th Floor Lecture Hall 
Tuesday  April 29, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Research  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research  
5:00  5:30  Problem Session Update  11th Floor Lecture Hall 
Wednesday  April 30, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Research  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research  
5:00  5:30  Problem Session Update  10th floor classroom 
Thursday  May 1, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Research  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research  
5:00  5:30  Problem Session Update  11th Floor Lecture Hall 
Friday  May 2, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Research  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Collaborative Space  
12:30  2:30  Break for Lunch  
2:30  5:00  Closing Session/WrapUp  11th Floor Lecture Hall 
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 328, 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, 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 socalled 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.



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 knearest 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  Yves van Gennip, University of Nottingham  11th Floor Lecture Hall  
11:30  1:00  Break for Lunch  
1:00  1:30  Distance geometry on graphs via synchronization  Mihai Cucuringu, UCLA  11th Floor Lecture Hall  
1:30  2:00  TBA  Michaela Puck Rombach, UCLA  11th Floor Lecture Hall  
2:00  2:15  Break  11th Floor Collaborative Space  
2:15  3:15  Applied Harmonic Analysis meets Compressed Sensing  Gitta Kutyniok, TU Berlin  11th Floor Lecture Hall  
4:45  5:45  Poster Session  11th Floor Collaborative Space 
Wednesday  February 5, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
10:00  11:00  Scalable Gaussian process models on matrices and tensors  Yuan Qi, Purdue University  11th Floor Lecture Hall  
11:00  11:30  Break  11th Floor Collaborative Space  
11:30  12:00  Spectral Methods for Analyzing Large Data  Blake Hunter, UCLA  11th Floor Lecture Hall  
12:00  12:30  Minimal Dirichlet energy partitions for graphs  Chris White, University of Texas at Austin  11th Floor Lecture Hall 
Thursday  February 6, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
10:00  11:00  Proximal splitting algorithms for two class and multiclass total variation clustering  Thomas Laurent, Loyola Marymount University  11th Floor Lecture Hall  
11:00  12:00  Pooling fidelity and phase recovery  Arthur Szlam, City College, CUNY  11th Floor Lecture Hall 
Friday  February 7, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:00  Random Graph Models for Image Patches  Francois Meyer, University of Colorado at Boulder  11th Floor Lecture Hall  
11:00  11:30  Break  11th Floor Collaborative Space  
11:30  12:00  Nonlocal Beltrami and Beltrami on graph  Dominique Zosso, UCLA  11th Floor Lecture Hall  
1:30  2:30  Graph cut, convex relaxation and continuous maxflow problems  Tai XueCheng, University of Bergen  10th Floor Classroom 
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 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.

Friday  February 21, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
10:00  11:50  Research Cluster: Graphs with incomplete information 
Friday  February 28, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
10:00  11:50  Research Cluster: Graphs with incomplete information 
Friday  March 7, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
10:00  11:50  Research Cluster: Graphs with incomplete information 
Friday  March 14, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
10:00  11:50  Research Cluster: Graphs with incomplete information 
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, 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 making graph structure techniques applicable to realworld 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 realworld 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 realworld 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 realworld graphs.


Thursday  April 24, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
8:30  9:00  Registration  11th Floor Collaborative Space  
9:00  10:20  Basic techniques of fixedparameter tractability (Part 1)  Saket Saurabh, Institute of Mathematical Sciences  11th Floor Lecture Hall  
10:30  11:00  Coffee/Tea Break  11th Floor Collaborative Space  
11:00  12:30  Basic techniques of fixedparameter tractability (Part 2)  Daniel Lokshtanov, University of Bergen  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Kernelization  Saket Saurabh, Institute of Mathematical Sciences  11th Floor Lecture Hall  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research 
Friday  April 25, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:20  Treewidth and applications  Fedor Fomin, University of Bergen  11th Floor Lecture Hall  
10:30  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  11:15  Open Problem Session  11th Floor Lecture Hall  
11:15  12:45  Minors and Algorithms  Erik Demaine, Massachusetts Institute of Technology  11th Floor Lecture Hall  
12:45  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research 
Saturday  April 26, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:20  Approximation Algorithms  Mohammad Taghi Hajiaghayi, University of Maryland  11th Floor Lecture Hall  
10:30  11:00  Coffee/Tea Break  11th Floor Collaborative Space  
11:00  12:30  Lower bounds  Daniel Marx, Hungarian Academy of Sciences (MTA)  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research 
Sunday  April 27, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:20  Separators  Daniel Marx, Hungarian Academy of Sciences (MTA)  11th Floor Lecture Hall  
10:30  11:00  Coffee/Tea Break  
11:00  12:30  Connecting to the RealWorld Applications  Blair Sullivan, North Carolina State University  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  
4:00  5:00  Research 
Monday  April 28, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Opening Session  11th Floor Lecture Hall  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research  
5:00  5:30  Problem Session Update  11th Floor Lecture Hall 
Tuesday  April 29, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Research  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research  
5:00  5:30  Problem Session Update  11th Floor Lecture Hall 
Wednesday  April 30, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Research  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research  
5:00  5:30  Problem Session Update  10th floor classroom 
Thursday  May 1, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Research  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Lecture Hall  
12:30  2:00  Break for Lunch  
2:00  3:30  Research  
3:30  4:00  Coffee/Tea Break  11th Floor Collaborative Space  
4:00  5:00  Research  
5:00  5:30  Problem Session Update  11th Floor Lecture Hall 
Friday  May 2, 2014  

Time  Description  Speaker  Location  Abstracts  Slides 
9:00  10:15  Research  
10:15  10:45  Coffee/Tea Break  11th Floor Collaborative Space  
10:45  12:00  Research  
12:00  12:30  Problem Session Update  11th Floor Collaborative Space  
12:30  2:30  Break for Lunch  
2:30  5:00  Closing Session/WrapUp  11th Floor Lecture Hall 
View inresidence dates for longterm visitors


