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.

  • Mohammadreza Aghajani
    (Brown University)
  • Suzanne Albers *
    (Humboldt-Universität)
  • Ian Alevy
    (Brown University)
  • John Augustine
    (Indian Institute of Technology)
  • Chen Avin *
    (Ben Gurion University of the Negev)
  • Nicole Beckage
    (University of Colorado)
  • Petra Berenbrink
    (Simon Fraser University)
  • Milan Bradonjic
    (Lucent Technologies Bell Laboratories)
  • Yixin Cao
    (Hungarian Academy of Sciences (MTA))
  • Flavio Chierichetti*
    (Università di Roma "La Sapienza")
  • Mihai Cucuringu
    (University of California, Los Angeles)
  • Artur Czumaj *
    (University of Warwick)
  • Lorenzo De Stefani
    (Università di Padova)
  • Thomas Dickerson
    (Brown University)
  • Devdatt Dubhashi
    (Chalmers University of Technology)
  • Robert Elsaesser *
    (Universität Salzburg)
  • Alessandro Epasto*
    (Università di Roma "La Sapienza")
  • Kyle Fox
    (University of Illinois at Urbana-Champaign)
  • Eli Fox-Epstein
    (Brown University)
  • Pierre Fraigniaud
    (Université de Paris VII (Denis Diderot))
  • Nathanaël François
    (Université de Paris VII (Denis Diderot))
  • Alan Frieze*
    (Carnegie Mellon University)
  • George Giakkoupis
    (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine)
  • Leslie Goldberg *
    (University of Oxford)
  • Michael Goodrich *
    (University of California, Irvine)
  • Steven Heilman
    (Courant Institute of Mathematical Sciences)
  • Steven Kim
    (Brown University)
  • Sungmin Kim
    (Ohio State University)
  • Valerie King *
    (University of Victoria)
  • Daniel Klein
    (Brown University)
  • Philip Klein
    (Brown University)
  • Bobby Kleinberg *
    (Cornell University)
  • Yiannis Koutis
    (University of Puerto Rico)
  • Ravi Kumar*
    (Google Inc.)
  • Silvio Lattanzi*
    (Google Inc.)
  • Christina Lee
    (Massachusetts Institute of Technology)
  • Stefano Leonardi*
    (Università di Roma "La Sapienza")
  • Gabor Lippner
    (Harvard University)
  • Zvi Lotker *
    (Ben Gurion University of the Negev)
  • Oren Louidor
    (Technion-Israel Institute of Technology)
  • Viacheslav Lyubchich
    (University of Waterloo)
  • Mohammad Mahdian*
    (Google Inc.)
  • Ahmad Mahmoody
    (Brown University)
  • William Martin
    (Worcester Polytechnic Institute)
  • Claire Mathieu
    (École Normale Supérieure)
  • David Meierfrankenfeld
    (Brown University)
  • Ekaterina Merkurjev
    (University of California, Los Angeles)
  • Francois Meyer
    (University of Colorado)
  • Vahab Mirrokni*
    (Google Inc.)
  • Michael Mitzenmacher*
    (Harvard University)
  • Danupon Nanongkai
    (Nanyang Technological University)
  • Gopal Pandurangan *
    (Nanyang Technological University)
  • Will Perkins
    (Georgia Institute of Technology)
  • Yvonne Anne Pignolet
    (ABB Corporate Research)
  • Mason Porter
    (University of Oxford)
  • Maithra Raghu
    (University of Cambridge)
  • Rajmohan Rajaraman *
    (Northeastern University)
  • Kavita Ramanan
    (Brown University)
  • Ben Raphael
    (Brown University)
  • R Ravi
    (Carnegie Mellon University)
  • Amanda Redlich
    (Bowdoin College)
  • David Richerby
    (University of Oxford)
  • Matteo Riondato
    (Brown University)
  • Igor Rivin
    (Temple University)
  • Scott Roche
    (Northeastern University)
  • Michaela Rombach
    (University of California, Los Angeles)
  • Piotr Sankowski*
    (University of Warsaw)
  • Thomas Sauerwald
    (University of Cambridge)
  • Devavrat Shah *
    (Massachusetts Institute of Technology)
  • David Shmoys
    (Cornell University)
  • Shashwat Silas
    (Brown University)
  • Alex Slivkins*
    (Microsoft Research)
  • Aravind Srinivasan*
    (University of Maryland)
  • Robert Stolz
    (University of the Virgin Islands)
  • Erik Sudderth
    (Brown University)
  • He Sun
    (Max-Planck-Institut für Informatik)
  • Charalampos Tsourakakis
    (Carnegie Mellon University)
  • Itzhak Turkel
    (Ben Gurion University of the Negev)
  • Eli Upfal *
    (Brown University)
  • Grigory Yaroslavtsev
    (Pennsylvania State University)
  • Gexin Yu
    (College of William and Mary)
  • Hang Zhou
    (École Normale Supérieure)
MondayMarch 17, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:50Registration: Stochastic Graph Models Workshop11th Floor Lecture Hall and Collaborative Space
9:50 - 10:00WelcomeICERM Director11th Floor Lecture Hall
10:00 - 10:45Evolutionary Dynamics on GraphsLeslie Ann Goldberg, University of Oxford11th Floor Lecture Hall
11:00 - 11:45Fast Testing of Graph PropertiesArtur Czumaj, University of Warwick11th Floor Lecture Hall
12:00 - 1:45Break for Lunch
1:45 - 2:30New Online Algorithms for Story Scheduling in Web AdvertisingSusanne Albers, TU Munich11th Floor Lecture Hall
2:45 - 3:30Trace Complexity of Network ReconstructionFlavio Chierichetti, Sapienza University of Rome11th Floor Lecture Hall
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Distributed Algorithmic Foundations of Dynamic NetworksGopal Pandurangan, Brown University and NTU, Singapore11th Floor Lecture Hall
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayMarch 18, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:30 - 10:00Open for Collaboration (Bagels and fruit provided)11th Floor Collaborative Space
10:00 - 10:45Force-Directed Graph Drawing Using Social Gravity and ScalingMichael Goodrich, University of California, Irvine11th Floor Lecture Hall
11:00 - 11:45Algorithms on Evolving Data SetsMohammad Mahdian, Google INC11th Floor Lecture Hall
12:00 - 1:45Break for Lunch
1:45 - 2:30Computing Stationary Distribution, LocallyDevavrat Shah, Massachusetts Institute of Technology11th Floor Lecture Hall
2:45 - 3:30Reconstructing Latent Similarities in a Multiplex Social NetworkAlex Slivkins, Microsoft Research11th Floor Lecture Hall
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Elite, Periphery and Symmetry in Social Networks- An Axiomatic ApproachChen Avin, Ben-Gurion University11th Floor Lecture Hall

WednesdayMarch 19, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:30 - 10:00Open for Collaboration (Bagels and fruit provided)11th Floor Collaborative Space
10:00 - 10:45Impromptu Updating in a Distributed Dynamic NetworkValerie King, University of Victoria11th Floor Lecture Hall
11:00 - 11:45Peeling AlgorithmsMichael Mitzenmacher, Harvard University11th Floor Lecture Hall
12:00 - 12:15Group Photo11th Floor Lecture Hall
12:15 - 1:45Break for Lunch
1:45 - 2:30On the Complexity of Information Spreading in Dynamic NetworksRajmohan Rajaraman, Northeastern University11th Floor Lecture Hall
2:45 - 3:30Power Law ComplexityPiotr Sankowski, University of Warsaw11th Floor Lecture Hall
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University10th Floor Classroom
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Chasing changes in dynamic structures.Eli Upfal, Brown University 11th Floor Lecture Hall
7:00 - 8:30Poster Session and Dessert Reception11th Floor Lecture Hall and Collaborative Space

ThursdayMarch 20, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:30 - 10:00Open for Collaboration (Bagels and fruit provided)11th Floor Collaborative Space
10:00 - 10:45The Power of Two Choices in Distributed VotingRobert Elsaesser, Universität Salzburg11th Floor Lecture Hall
11:00 - 11:45Efficient computation of the weighted clustering coefficientStefano Leonardi, Sapienza University of Rome11th Floor Lecture Hall
12:00 - 1:45Break for Lunch
1:45 - 2:30Improved bounds and algorithms for graph cuts and network reliabilityAravind Srinivasan, University of Maryland11th Floor Lecture Hall
2:45 - 3:30Online Stochastic Matching- New Results and Open ProblemsVahab Mirrokni, Google Inc.11th Floor Lecture Hall
3:30 - 3:35Please take a moment to complete the survey that was distributed by email.
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Similarity Ranking in Large-Scale Bipartite GraphsAlessandro Epasto, Universita di Roma La Sapienza11th Floor Lecture Hall

FridayMarch 21, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:30 - 10:00Open for Collaboration (Bagels and fruit provided)11th Floor Collaborative Space
10:00 - 10:45Randomly coloring random graphsAlan Frieze, Carnegie Mellon University11th Floor Lecture Hall
11:00 - 11:45Estimating Network ParametersRavi Kumar, Google Inc.11th Floor Lecture Hall
12:00 - 1:30Break for Lunch
1:30 - 2:30Theory Seminar (ongoing semester seminar)- Improved Approximations for Graph-TSP in Regular GraphsR. Ravi, Carnegie Mellon University11th Floor Lecture Hall
2:45 - 3:30An Efficient reconciliation algorithm for social networksSilvio Lattanzi, Google Inc.11th Floor Lecture Hall
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45On the Glass Ceiling Effect in Social NetworksZvi Lotker, Ben-Gurion University of the Negev and Claire Mathieu, Brown University11th Floor Lecture Hall