Organizing Committee
Abstract

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.

Image for "Stochastic Graph Models"

Confirmed Speakers & Participants

Talks will be presented virtually or in-person as indicated in the schedule below.

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, March 17, 2014
TimeEventLocationMaterials
9:00 - 9:50am EDTRegistration: Stochastic Graph Models Workshop11th Floor Lecture Hall and Collaborative Space 
9:50 - 10:00am EDTWelcome - ICERM Director11th Floor Lecture Hall 
10:00 - 10:45am EDTEvolutionary Dynamics on Graphs - Leslie Ann Goldberg, University of Oxford11th Floor Lecture Hall
11:00 - 11:45am EDTFast Testing of Graph Properties - Artur Czumaj, University of Warwick11th Floor Lecture Hall
12:00 - 1:45pm EDTBreak for Lunch  
1:45 - 2:30pm EDTNew Online Algorithms for Story Scheduling in Web Advertising - Susanne Albers, TU Munich11th Floor Lecture Hall
2:45 - 3:30pm EDTTrace Complexity of Network Reconstruction - Flavio Chierichetti, Sapienza University of Rome11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTDistributed Algorithmic Foundations of Dynamic Networks - Gopal Pandurangan, Brown University and NTU, Singapore11th Floor Lecture Hall
5:00 - 6:30pm EDTWelcome Reception11th Floor Collaborative Space 
Tuesday, March 18, 2014
TimeEventLocationMaterials
9:30 - 10:00am EDTOpen for Collaboration (Bagels and fruit provided)11th Floor Collaborative Space 
10:00 - 10:45am EDTForce-Directed Graph Drawing Using Social Gravity and Scaling - Michael Goodrich, University of California, Irvine11th Floor Lecture Hall
11:00 - 11:45am EDTAlgorithms on Evolving Data Sets - Mohammad Mahdian, Google INC11th Floor Lecture Hall
12:00 - 1:45pm EDTBreak for Lunch  
1:45 - 2:30pm EDTComputing Stationary Distribution, Locally - Devavrat Shah, Massachusetts Institute of Technology11th Floor Lecture Hall
2:45 - 3:30pm EDTReconstructing Latent Similarities in a Multiplex Social Network - Alex Slivkins, Microsoft Research11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTElite, Periphery and Symmetry in Social Networks- An Axiomatic Approach - Chen Avin, Ben-Gurion University11th Floor Lecture Hall
Wednesday, March 19, 2014
TimeEventLocationMaterials
9:30 - 10:00am EDTOpen for Collaboration (Bagels and fruit provided)11th Floor Collaborative Space 
10:00 - 10:45am EDTImpromptu Updating in a Distributed Dynamic Network - Valerie King, University of Victoria11th Floor Lecture Hall
11:00 - 11:45am EDTPeeling Algorithms - Michael Mitzenmacher, Harvard University11th Floor Lecture Hall
12:00 - 12:15pm EDTGroup Photo11th Floor Lecture Hall 
12:15 - 1:45pm EDTBreak for Lunch  
1:45 - 2:30pm EDTOn the Complexity of Information Spreading in Dynamic Networks - Rajmohan Rajaraman, Northeastern University11th Floor Lecture Hall
2:45 - 3:30pm EDTPower Law Complexity - Piotr Sankowski, University of Warsaw11th Floor Lecture Hall
3:00 - 5:20pm EDTOptimization Algorithms for Planar Graphs (ongoing semester course) - Phil Klein, Brown University and Claire Mathieu, Brown University10th Floor Classroom 
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTChasing changes in dynamic structures. - Eli Upfal, Brown University 11th Floor Lecture Hall 
7:00 - 8:30pm EDTPoster Session and Dessert Reception11th Floor Lecture Hall and Collaborative Space 
Thursday, March 20, 2014
TimeEventLocationMaterials
9:30 - 10:00am EDTOpen for Collaboration (Bagels and fruit provided)11th Floor Collaborative Space 
10:00 - 10:45am EDTThe Power of Two Choices in Distributed Voting - Robert Elsaesser, Universität Salzburg11th Floor Lecture Hall 
11:00 - 11:45am EDTEfficient computation of the weighted clustering coefficient - Stefano Leonardi, Sapienza University of Rome11th Floor Lecture Hall
12:00 - 1:45pm EDTBreak for Lunch  
1:45 - 2:30pm EDTImproved bounds and algorithms for graph cuts and network reliability - Aravind Srinivasan, University of Maryland11th Floor Lecture Hall
2:45 - 3:30pm EDTOnline Stochastic Matching- New Results and Open Problems - Vahab Mirrokni, Google Inc.11th Floor Lecture Hall
3:30 - 3:35pm EDTPlease take a moment to complete the survey that was distributed by email.  
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTSimilarity Ranking in Large-Scale Bipartite Graphs - Alessandro Epasto, Universita di Roma La Sapienza11th Floor Lecture Hall
Friday, March 21, 2014
TimeEventLocationMaterials
9:30 - 10:00am EDTOpen for Collaboration (Bagels and fruit provided)11th Floor Collaborative Space 
10:00 - 10:45am EDTRandomly coloring random graphs - Alan Frieze, Carnegie Mellon University11th Floor Lecture Hall
11:00 - 11:45am EDTEstimating Network Parameters - Ravi Kumar, Google Inc.11th Floor Lecture Hall
12:00 - 1:30pm EDTBreak for Lunch  
1:30 - 2:30pm EDTTheory Seminar (ongoing semester seminar)- Improved Approximations for Graph-TSP in Regular Graphs - R. Ravi, Carnegie Mellon University11th Floor Lecture Hall
2:45 - 3:30pm EDTAn Efficient reconciliation algorithm for social networks - Silvio Lattanzi, Google Inc.11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTOn the Glass Ceiling Effect in Social Networks - Zvi Lotker, Ben-Gurion University of the Negev and Claire Mathieu, Brown University11th Floor Lecture Hall

Associated Semester Workshops

Network Science and Graph Algorithms
Image for "Network Science and Graph Algorithms"
Semidefinite Programming and Graph Algorithms
Image for "Semidefinite Programming and Graph Algorithms"

Research Clusters

Lecture Videos

On the Glass Ceiling Effect in Social Networks

Zvi Lotker
Ben Gurion University of the Negev
March 21, 2014

Randomly coloring random graphs

Alan Frieze
Carnegie Mellon University
March 21, 2014

Similarity Ranking in Large-Scale Bipartite Graphs

Alessandro Epasto
Università di Roma "La Sapienza"
March 20, 2014

Peeling Algorithms

Michael Mitzenmacher
Harvard University
March 19, 2014

Algorithms on Evolving Data Sets

Mohammad Mahdian
Google Inc.
March 18, 2014

Force-Directed Graph Drawing Using Social Gravity and Scaling

Michael Goodrich
University of California, Irvine
March 18, 2014

Distributed Algorithmic Foundations of Dynamic Networks

Gopal Pandurangan
Nanyang Technological University
March 17, 2014