Home

ICERM Semester Program on "Network Science and Graph Algorithms"
(February 3, 2014 - May 9, 2014)

CLICK HERE TO PARTICIPATE
Organizing Committee
  • 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)

Picture

[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.



**Long-Term Participants
View in-residence dates for long-term visitors
  • Emmanuel Abbe
    (Princeton University)
  • Rediet Abebe
    (University of Cambridge)
  • Aaron Adcock
    (Stanford University)
  • Shahriar Afkhami
    (New Jersey Institute of Technology)
  • Mohammadreza Aghajani
    (Brown University)
  • Derek Aguiar
    (Brown University)
  • Amir Ali Ahmadi
    (Massachusetts Institute of Technology)
  • Mark Ainsworth
    (Brown University)
  • Suzanne Albers
    (Humboldt-Universität)
  • Ian Alevy
    (Brown University)
  • Joe Alexandersen
    (Technical University of Denmark)
  • Monther Alfuraidan
    (King Fahd University of Petroleum and Minerals)
  • Maryam Aliakbarpour
    (Massachusetts Institute of Technology)
  • Zeyuan Allen-Zhu
    (Massachusetts Institute of Technology)
  • Anima Anandkumar
    (University of California, Irvine)
  • Harbir Antil
    (George Mason University)
  • Douglas Arnold
    (University of Minnesota)
  • Sanjeev Arora
    (Princeton University)
  • David Aucsmith
    (Microsoft Research)
  • John Augustine **
    (Indian Institute of Technology)
  • Chen Avin **
    (Ben Gurion University of the Negev)
  • Haim Avron
    (IBM Corporation)
  • Constantin Bacuta
    (University of Delaware)
  • Nikhil Bansal
    (Technische Universiteit Eindhoven)
  • Boaz Barak
    (Microsoft Research)
  • Guillaume Basse
    (Harvard University)
  • Devasis Bassu
    (Applied Communication Sciences)
  • Frank Bauer
    (Harvard University)
  • Yuri Bazilevs
    (University of California, San Diego)
  • Nicole Beckage
    (University of Colorado)
  • Josh Benaloh
    (Microsoft Research)
  • Emanuel Ben-David
    (Columbia University)
  • Ioana Bercea
    (University of Maryland)
  • Petra Berenbrink
    (Simon Fraser University)
  • Tejal Bhamre
    (Princeton University)
  • Daniel Bienstock **
    (Columbia University)
  • Amartya Biswas
    (Massachusetts Institute of Technology)
  • Pablo Blanco
    (National Laboratory for Scientific Computing)
  • Daniele Boffi
    (Università di Pavia)
  • Erik Boman
    (Sandia National Laboratories)
  • Christian Borgs
    (Microsoft Research)
  • Christos Boutsidis
    (Yahoo! Inc.)
  • Milan Bradonjic
    (Bell Labs, Alcatel-Lucent)
  • Xavier Bresson
    (Université de Lausanne)
  • Franco Brezzi
    (Consiglio Nazionale delle Ricerche (CNR))
  • Jop Briët
    (New York University)
  • Martina Bukac
    (University of Pittsburgh)
  • Daniela Calvetti
    (Case Western Reserve University)
  • Suncica Canic
    (University of Houston)
  • Pierre Cantin
    (Électricité de France)
  • Yixin Cao **
    (Hungarian Academy of Sciences (MTA))
  • Lawrence Carin
    (Duke University)
  • Marco Carvalho
    (Florida Institute of Technology)
  • Juan Cebral
    (George Mason University)
  • Amit Chakrabarti
    (Dartmouth College)
  • Erin Chambers
    (St. Louis University)
  • Venkat Chandrasekeran
    (California Institute of Technology)
  • Jennifer Chayes
    (Microsoft Research)
  • Feng Chen
    (Brown University)
  • Long Chen
    (University of California, Irvine)
  • Yanlai Chen
    (University of Massachusetts)
  • Zhiming Chen
    (Chinese Academy of Sciences)
  • Flavio Chierichetti
    (Università di Roma "La Sapienza")
  • Peter Chin
    (Boston University)
  • Rajesh Chitnis
    (University of Maryland)
  • Krzysztof Choromanski
    (Google Inc.)
  • Rasmus Christiansen
    (Technical University of Denmark)
  • Bong Jae Chung
    (George Mason University)
  • Michael Cohen
    (Massachusetts Institute of Technology)
  • Henry Cohn
    (Microsoft Research)
  • Mihai Cucuringu **
    (University of California, Los Angeles)
  • Artur Czumaj
    (University of Warwick)
  • Daniel Dadush
    (New York University)
  • Erik Demaine
    (Massachusetts Institute of Technology)
  • Leszek Demkowicz
    (University of Texas at Austin)
  • Lorenzo De Stefani **
    (Università di Padova)
  • Paolo Di Achille
    (Yale University)
  • Thomas Dickerson **
    (Brown University)
  • Luis Dorfmann
    (Tufts University)
  • Xinjie Duan
    (University of Pittsburgh)
  • Devdatt Dubhashi
    (Chalmers University of Technology)
  • Sam Dudley
    (Brown University)
  • Ioana Dumitriu
    (University of Washington)
  • Andrea Dzinbek
    (SUNY)
  • Michela Egidi
    (University of Durham)
  • Laura Ellwein
    (Virginia Commonwealth University)
  • Robert Elsaesser
    (Universität Salzburg)
  • Alessandro Epasto
    (Università di Roma "La Sapienza")
  • Hossein Esfandiari
    (University of Maryland)
  • Lledó Esquerra-Ortells
    (University of Colorado)
  • Richard Falk
    (Rutgers University)
  • Carrie Falke
    (Louisiana Tech University)
  • Angiolo Farina
    (Università di Firenze)
  • Hamza Fawzi
    (Massachusetts Institute of Technology)
  • Pedro Felzenszwalb
    (Brown University)
  • Flavio Fenton
    (Georgia Institute of Technology)
  • Carlos Figueroa
    (King's College)
  • Enrico Filippi
    (Brown University)
  • Arjuna Flenner **
    (Naval Air Warfare Center)
  • Fedor Fomin
    (University of Bergen)
  • Davide Forti
    (École Polytechnique Fédérale de Lausanne (EPFL))
  • 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))
  • Cameron Freer
    (Massachusetts Institute of Technology)
  • Alan Frieze
    (Carnegie Mellon University)
  • Lorenzo Fusi
    (Università di Firenze)
  • Cristina Garcia
    (Claremont Graduate University)
  • Nicolas Garcia **
    (Carnegie Mellon University)
  • Paolo Gatto
    (Brown University)
  • Rong Ge
    (Microsoft Research)
  • Luca Gerardo Giorda
    (Basque Center for Applied Mathematics)
  • George Giakkoupis
    (Institut National de Recherche en Informatique Automatique (INRIA)-Lorraine)
  • Anna Gilbert
    (University of Michigan)
  • Andrew Gillette
    (University of Arizona)
  • David Gillman
    (New College of Florida)
  • Roland Glowinski
    (University of Houston)
  • Christian Glusa
    (Brown University)
  • Michel Goemans
    (Massachusetts Institute of Technology)
  • Daniel Golbert
    (Brown University)
  • Leslie Goldberg
    (University of Oxford)
  • Michael Goodrich
    (University of California, Irvine)
  • Venu Gopal
    (Brown University)
  • Jay Gopalakrishnan
    (Portland State University)
  • Themistoklis Gouleakis
    (Massachusetts Institute of Technology)
  • Fan Chung Graham
    (University of California, San Diego)
  • Stephen Greenwald
    (Queen Mary and Westfield College)
  • Pierre Gremaud
    (North Carolina State University)
  • Leopold Grinberg
    (IBM)
  • Sebastian Gruler
    (Universität Konstanz)
  • David Guarrera
    (QS2/DARPA)
  • Mamikon Gulian
    (Brown University)
  • Viatcheslav Gurev
    (IBM)
  • Venkatesan Guruswami
    (Carnegie Mellon University)
  • Johnny Guzman
    (Brown University)
  • MohammadTaghi Hajiaghayi
    (University of Maryland)
  • John Harer
    (Duke University)
  • Steven Heilman **
    (Courant Institute of Mathematical Sciences)
  • Bruce Hendrickson
    (Sandia National Laboratories)
  • Nadia Heninger
    (University of Pennsylvania)
  • Ralf Hiptmair
    (ETH)
  • Anil Hirani
    (University of Illinois at Urbana-Champaign)
  • Jeffrey Hoffstein
    (Brown University)
  • Emilie Hogan
    (Pacific Northwest National Laboratory)
  • Michael Holst
    (University of California, San Diego)
  • Jeremy Hoskins
    (University of Michigan)
  • Huiyi Hu **
    (University of California, Los Angeles)
  • Jun Hu
    (Beijing (Peking) University)
  • Xiaozhe Hu
    (Pennsylvania State University)
  • Jay Humphrey
    (Yale University)
  • Blake Hunter **
    (University of California, Los Angeles)
  • Elizabeth Iffrig
    (Georgia Institute of Technology)
  • Sorin Istrail
    (Brown University)
  • Sameer Iyer
    (Brown University)
  • Majid Janzamin
    (University of California, Irvine)
  • John Johnson
    (Pacific Northwest National Laboratory)
  • Peter Jones
    (Yale University)
  • Satyen Kale
    (Yahoo! Inc.)
  • Sunil Kandel
    (Oakland University)
  • Michael Kapralov
    (Massachusetts Institute of Technology)
  • Howard Karloff
    (Yahoo! Inc.)
  • Alain Karma
    (Northeastern University)
  • George Karniadakis
    (Brown University)
  • Jonathan Kelner
    (Massachusetts Institute of Technology)
  • Yvonne Kemper
    (National Institute of Standards and Technology)
  • Franklin Kenter
    (Rice University)
  • Richard Kenyon
    (Brown University)
  • Chiheon Kim
    (Massachusetts Institute of Technology)
  • Steven Kim
    (Brown University)
  • Sungmin Kim
    (Ohio State University)
  • Tae Kim
    (Brown University)
  • Valerie King
    (University of Victoria)
  • Slav Kirov **
    (Carnegie Mellon University)
  • Daniel Klein
    (Brown University)
  • Philip Klein **
    (Brown University)
  • Bobby Kleinberg
    (Cornell University)
  • Caroline Klivans
    (Brown University)
  • Andrew Knyazev
    (Mitsubishi Electric Research Laboratories)
  • Alexandra Kolla
    (University of Illinois at Urbana-Champaign)
  • Risi Kondor
    (University of Chicago)
  • Gideon Koren
    (Brown University)
  • Yiannis Koutis **
    (University of Puerto Rico)
  • Ravi Kumar
    (Google Inc.)
  • Gitta Kutyniok **
    (TU Berlin)
  • Hyun-Kyoung Kwon
    (University of Alabama)
  • Rasmus Kyng
    (Yale University)
  • Matthew Langston
    (Reservoir Labs Inc)
  • Michael Langston
    (University of Tennessee)
  • Jean Lasserre
    (Centre National de la Recherche Scientifique (CNRS))
  • Silvio Lattanzi
    (Google Inc.)
  • Kevin Lau
    (University of London)
  • Monique Laurent
    (Center for Mathematics and Computer Science (CWI))
  • Thomas Laurent **
    (Loyola Marymount University)
  • Roy Lederman
    (Yale University)
  • Christina Lee
    (Massachusetts Institute of Technology)
  • James Lee
    (University of Washington)
  • Youngju Lee
    (Texas State University-San Marcos)
  • Stefano Leonardi
    (Università di Roma "La Sapienza")
  • Gilad Lerman
    (University of Minnesota)
  • Dmitriy Leykekhman
    (University of Connecticut)
  • Olivier Lezoray
    (Université de Caen)
  • Xingjie Li
    (Brown University)
  • Xuejin Li
    (Brown University)
  • Zhen Li
    (Brown University)
  • Vahid Liaghat
    (University of Maryland)
  • Gabor Lippner
    (Harvard University)
  • Dexter Liu
    (University of Georgia)
  • Shiping Liu
    (University of Durham)
  • Daniel Lokshtanov
    (University of Bergen)
  • Zvi Lotker
    (Ben Gurion University of the Negev)
  • Oren Louidor
    (Technion-Israel Institute of Technology)
  • Torbjörn Lundh
    (Chalmers University of Technology)
  • Mitchell Luskin
    (University of Minnesota)
  • Viacheslav Lyubchich
    (University of Waterloo)
  • Yicong Ma
    (Pennsylvania State University)
  • Yvon Maday
    (Brown University)
  • Aleksander Madry
    (École Polytechnique Fédérale de Lausanne (EPFL))
  • Mauro Maggioni
    (Duke University)
  • Sepideh Mahabadi
    (Massachusetts Institute of Technology)
  • Mohammad Mahdian
    (Google Inc.)
  • Ahmad Mahmoody **
    (Brown University)
  • Michael Mahoney
    (University of California, Berkeley)
  • Anthony Man-Cho So
    (Chinese University of Hong Kong)
  • Donatella Marini
    (Università di Pavia)
  • Alison Marsden
    (University of California, San Diego)
  • William Martin **
    (Worcester Polytechnic Institute)
  • Gunnar Martinsson
    (University of Colorado)
  • Daniel Marx
    (Hungarian Academy of Sciences (MTA))
  • Monaldo Mastrolilli
    (IDSIA)
  • Claire Mathieu **
    (École Normale Supérieure)
  • Charalampos Mavroforakis
    (Boston University)
  • Patrick McDonald
    (New College of Florida)
  • Andrew McGregor
    (University of Massachusetts)
  • David Meierfrankenfeld **
    (Brown University)
  • Ekaterina Merkurjev **
    (University of California, Los Angeles)
  • Maximilian Metti
    (Pennsylvania State University)
  • Francois Meyer
    (University of Colorado)
  • Gary Miller
    (Carnegie Mellon University)
  • Vahab Mirrokni
    (Google Inc.)
  • Michael Mitzenmacher
    (Harvard University)
  • Ankur Moitra
    (Massachusetts Institute of Technology)
  • Morteza Monemizadeh
    (University of Maryland)
  • Nathan Monnig
    (University of Colorado)
  • Bill Moran
    (University of Melbourne)
  • Jason Morton
    (Pennsylvania State University)
  • Elchanan Mossel
    (University of California, Berkeley)
  • Shay Mozes
    (Interdisciplinary Center for Neural Computation at Hebrew University)
  • Lucas Muller
    (Università di Trento)
  • David Naccache
    (École Normale Supérieure)
  • Sobhan Naderi Parizi
    (Brown University)
  • Krishna Nand
    (Brown University)
  • Danupon Nanongkai **
    (Nanyang Technological University)
  • Assaf Naor
    (New York University)
  • Joe Neeman
    (University of Texas at Austin)
  • Michael Neilan
    (University of Pittsburgh)
  • Pedja Neskovic
    (Office of Naval Research)
  • Linda Ness
    (Applied Communication Sciences)
  • Hoi Nguyen
    (Ohio State University)
  • Huy Le Nguyen
    (Princeton University)
  • Ricardo Nochetto
    (University of Maryland)
  • Michael O'Brien
    (North Carolina State University)
  • Mette Olufsen
    (North Carolina State University)
  • Lorenzo Orecchia
    (Massachusetts Institute of Technology)
  • Saulo Orizaga
    (Iowa State University)
  • Sean O'Rourke
    (Yale University)
  • John Oshinski
    (Emory University)
  • Andrei Osipov
    (Yale University)
  • Braxton Osting **
    (University of California, Los Angeles)
  • Shayan Oveis-Gharan
    (Stanford University)
  • Jakub Pachocki
    (Carnegie Mellon University)
  • Gopal Pandurangan **
    (Nanyang Technological University)
  • Debmalya Panigrahi
    (Duke University)
  • Charalampos Papmanthou
    (University of Maryland)
  • Pablo Parrilo
    (Massachusetts Institute of Technology)
  • Dusko Pavlovic
    (University of Hawaii at Manoa)
  • David Peleg
    (Weizmann Institute of Science)
  • Richard Peng
    (Massachusetts Institute of Technology)
  • Zhangli Peng
    (Massachusetts Institute of Technology)
  • Paris Perdikaris
    (Brown University)
  • Will Perkins
    (Georgia Institute of Technology)
  • Gustavo Perla Menzala
    (Laboratorio Nacional de Computacao Cientifica)
  • Thomas Peters
    (University of Connecticut)
  • Lam Pham
    (Yale University)
  • Julie Phillippi
    (University of Pittsburgh)
  • David Phillips
    (U.S. Naval Academy)
  • Andrea Pietracaprina **
    (Università di Padova)
  • Yvonne Anne Pignolet
    (ABB Corporate Research)
  • Richard Pinch
    (Government Communications Headquarters)
  • Jill Pipher
    (Institute for Computational and Experimental Research in Mathematics (ICERM))
  • Sebastian Pokutta
    (Georgia Institute of Technology)
  • Andrew Pollington
    (National Science Foundation)
  • Mason Porter **
    (University of Oxford)
  • Geppino Pucci **
    (Università di Padova)
  • Manish Purohit
    (University of Maryland)
  • Yuan (Alan) Qi
    (Purdue University)
  • Saad Quader
    (University of Connecticut)
  • Alfio Quarteroni
    (École Polytechnique Fédérale de Lausanne (EPFL))
  • Prasad Raghavendra
    (University of California, Berkeley)
  • Maithra Raghu
    (University of Cambridge)
  • Rajmohan Rajaraman
    (Northeastern University)
  • Kavita Ramanan
    (Brown University)
  • Sanjay Ramassamy
    (Brown University)
  • Ramsharan Rangarajan
    (Brown University)
  • Anup Rao
    (Yale University)
  • Ben Raphael **
    (Brown University)
  • Sofya Raskhodnikova
    (Boston University)
  • Ramamoorthi Ravi
    (Carnegie Mellon University)
  • Benjamin Recht
    (University of California, Berkeley)
  • Amanda Redlich **
    (Bowdoin College)
  • Erzsebet Regan
    (Harvard University)
  • Felix Reidl
    (RWTH Aachen)
  • John Rice
    (IBM)
  • David Richerby
    (University of Oxford)
  • Matteo Riondato
    (Brown University)
  • Anne Robertson
    (University of Pittsburgh)
  • Scott Roche **
    (Northeastern University)
  • Vladimir Rokhlin
    (Yale University)
  • Michaela Rombach **
    (University of California, Los Angeles)
  • Jenn Rossmann
    (Lafayette College)
  • Ronitt Rubinfield
    (Massachusetts Institute of Technology)
  • Mark Rudelson
    (University of Michigan)
  • Cody Rutledge
    (Brown University)
  • Sushant Sachdeva
    (Yale University)
  • Venkatesh Saligrama
    (Boston University)
  • David Saltman
    (Center for Communications Research)
  • Habib Samady
    (Emory University)
  • Manuel Sanchez-Uribe
    (Brown University)
  • Fernando Sanchez Villaamil
    (RWTH Aachen)
  • Piotr Sankowski
    (University of Warsaw)
  • Marcus Sarkis
    (Worcester Polytechnic Institute)
  • Kanthi Sarpatwar
    (University of Maryland)
  • Thomas Sauerwald
    (University of Cambridge)
  • James Saunderson
    (Massachusetts Institute of Technology)
  • Saket Saurabh
    (Institute of Mathematical Sciences)
  • Aaron Schild
    (Princeton University)
  • Joachim Schöberl
    (Technische Universität Wien)
  • Bernd Schroeder
    (Louisiana Tech University)
  • Devavrat Shah
    (Massachusetts Institute of Technology)
  • Simon Shaw
    (Brunel University)
  • Ke Shi
    (Texas A & M University)
  • David Shmoys
    (Cornell University)
  • Chi-Wang Shu
    (Brown University)
  • Shashwat Silas
    (Brown University)
  • Joseph Silverman
    (Brown University)
  • Oliva Simpson
    (University of California, San Diego)
  • Amit Singer
    (Princeton University)
  • Ali Sinop
    (Institute for Advanced Study)
  • Jon Sjogren
    (Towson State University)
  • Dejan Slepčev **
    (Carnegie Mellon University)
  • Alex Slivkins
    (Microsoft Research)
  • Michael Snarski
    (Brown University)
  • Erkki Somersalo
    (Case Western Reserve University)
  • Eric Sommers
    (National Science Foundation)
  • Aikaterini Sotiraki
    (Massachusetts Institute of Technology)
  • Renata Sotirov
    (Tilburg University)
  • Raymond Spiteri
    (University of Saskatchewan)
  • Aravind Srinivasan
    (University of Maryland)
  • Nikhil Srivastava
    (Microsoft Research India)
  • David Steurer
    (Cornell University)
  • Robert Stolz
    (University of the Virgin Islands)
  • Gilbert Strang
    (Massachusetts Institute of Technology)
  • Erik Sudderth
    (Brown University)
  • Blair Sullivan
    (North Carolina State University)
  • He Sun
    (Max-Planck-Institut für Informatik)
  • Pengtao Sun
    (University of Nevada)
  • Yi Sun
    (University of South Carolina)
  • Arthur Szlam **
    (City College, CUNY)
  • Marcela Szopos
    (Université de Strasbourg I (Louis Pasteur))
  • Xue-Cheng Tai **
    (University of Bergen)
  • Christino Tamon
    (Clarkson University)
  • W. Robert Taylor
    (Emory University)
  • Evimaria Terzi
    (Boston University)
  • Vladimir Tonchev
    (Michigan Technological University)
  • Frank Tong
    (Emory University)
  • Charalampos Tsourakakis **
    (Carnegie Mellon University)
  • Itzhak Turkel
    (Ben Gurion University of the Negev)
  • Lara Ruth Turner
    (University of Vienna )
  • Francisco Unda
    (Massachusetts Institute of Technology)
  • Eli Upfal **
    (Brown University)
  • Ali Vakilian
    (Massachusetts Institute of Technology)
  • Arturo Valentin
    (University of Pittsburgh)
  • Frank Vallentin
    (Universität zu Köln)
  • Yves van Gennip **
    (University of Nottingham)
  • Alessandro Veneziani
    (Emory University)
  • Daniele Venturi
    (Brown University)
  • Nisheeth Vishnoi
    (Microsoft Research India)
  • James von Brecht **
    (University of California, Los Angeles)
  • Ulrike von Luxburg **
    (Universität Hamburg)
  • Sergey Voronin
    (University of Colorado)
  • Vladislav Voroninski
    (Massachusetts Institute of Technology)
  • Van Vu
    (Yale University)
  • Ralph Wachter
    (National Science Foundation)
  • Homer Walker
    (Institute for Computational and Experimental Research in Mathematics (ICERM))
  • Shawn Walker
    (Louisiana State University)
  • Fei Wang
    (Pennsylvania State University)
  • Ke Wang
    (University of Minnesota)
  • Lu Wang
    (Pennsylvania State University)
  • Rachel Ward
    (University of Texas at Austin)
  • Mario Sansuke Watanabe
    (Laboratorio Nacional de Computacao Cientifica)
  • Paul Watton
    (University of Oxford)
  • Chelsea Weaver
    (University of California, Davis)
  • Stephanie Wehner
    (National University of Singapore)
  • Kilian Weinberger
    (Washington University)
  • Mary Wheeler
    (University of Texas at Austin)
  • Christopher White **
    (University of Texas at Austin)
  • Rebecca Willett
    (University of Wisconsin)
  • James Williams
    (Yale University)
  • Raimond Winslow
    (Johns Hopkins University)
  • Ragnar Winther
    (University of Oslo)
  • Alexandra Witthoft
    (Brown University)
  • Carol Woodward
    (Lawrence Livermore National Laboratory)
  • Joseph Woodworth **
    (University of California, Los Angeles)
  • Christian Wulff-Nilsen
    (University of Copenhagen)
  • Xiaoqing Xing
    (South China (Huanan) Normal University)
  • Ghomglei Xiong
    (Cornell University)
  • Jinchao Xu
    (Pennsylvania State University)
  • Shen Chen Xu
    (Carnegie Mellon University)
  • Kai Yang
    (Pennsylvania State University)
  • Alireza Yazdani
    (Brown University)
  • Anak Yodpinyanee
    (Massachusetts Institute of Technology)
  • Neal Young **
    (University of California, Riverside)
  • Gexin Yu
    (College of William and Mary)
  • Yue Yu
    (Brown University)
  • Luca Zanetti
    (Universität des Saarlandes)
  • Mohsen Zayernouri
    (Brown University)
  • Pingwen Zhang
    (Beijing (Peking) University)
  • Shuo Zhang
    (Chinese Academy of Sciences)
  • Teng Zhang
    (Princeton University)
  • Xiangxiong Zhang
    (Massachusetts Institute of Technology)
  • Bingyu Zhao
    (Brown University)
  • Liuqiang Zhong
    (South China (Huanan) Normal University)
  • Hang Zhou **
    (École Normale Supérieure)
  • Yuan Zhou
    (Carnegie Mellon University)
  • Yao Zhu
    (Purdue University)
  • Ludmil Zikatanov
    (Pennsylvania State University)
  • Dominique Zosso
    (University of California, Los Angeles)
  • Paolo Zunino
    (University of Pittsburgh)

MondayFebruary 3, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:30 - 1:35Network Science and Graph Algorithms Semester Program Opening Welcome11th Floor Lecture Hall
1:35 - 2:05Graduate student introductionsThomas 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 Angeles11th Floor Lecture Hall
2:05 - 2:105-minute Postdoc introductionMihai Cucuringu, University of California, Los Angeles11th Floor Lecture Hall
2:10 - 2:155-minute Postdoc introductionKyle Fox, University of Illinois at Urbana-Champaign11th Floor Lecture Hall
2:15 - 2:205-minute Postdoc introductionBlake Hunter, University of California, Los Angeles11th Floor Lecture Hall
2:20 - 2:255-minute Postdoc introductionAmanda Redlich, Bowdoin College11th Floor Lecture Hall
2:30 - 2:355-minute Postdoc introductionMichaela Rombach, University of California, Los Angeles11th Floor Lecture Hall
2:35 - 2:405-minute Postdoc introductionCharalampos Tsourakakis, Carnegie Mellon University11th Floor Lecture Hall
2:40 - 2:455-minute Postdoc introductionGrigory Yaroslavtsev, Pennsylvania State University11th Floor Lecture Hall
2:45 - 2:505-minute Postdoc introductionDominique Zosso, Universtiy of California, Los Angeles11th Floor Lecture Hall
2:50 - 3:00Coffee Break11th Floor Collaborative Space
3:00 - 5:00Informal Faculty Introductions11th Floor Lecture Hall

TuesdayFebruary 4, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayFebruary 5, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:00 - 5:20Topics in Advanced Algorithms (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayFebruary 6, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffe Break11th Floor Collaborative Space

FridayFebruary 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:00 - 2:15Theory Seminar11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayFebruary 10, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 8:55Registration: Semidefinite Programming and Graph Algorithms Workshop11th Floor Collaborative Space
8:55 - 9:00WelcomeICERM Director11th Floor Lecture Hall
9:00 - 9:45The Moment-LP and Moment-SOS approaches in polynomial optimizationJean Lasserre, Centre National de la Recherche Scientifique (CNRS)11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Rounding Sum of Squares RelaxationsBoaz Barak, Microsoft Research11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15TBAJonathan Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall
12:30 - 2:30Break for Lunch
2:30 - 3:15Convergence of SDP hierarchies using kernel based methodsStephanie Wehner, National University of Singapore11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break10th Floor Collaborative Space
4:00 - 4:45Vertical versus horizontal Poincare inequalitiesAssaf Naor, New York University11th Floor Lecture Hall
PDF
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayFebruary 11, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Expander flows, Geometric embeddings and Graph PartitioningClaire Mathieu, Ecole Normale Superieure11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Towards a Better Approximation of Sparsest Cut?Sanjeev Arora, Princeton University11th Floor Lecture Hall
PDF
11:30 - 12:15Going off the gridBenjamin Recht, University of California, Berkeley11th Floor Lecture Hall
PDF
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15On the existence of 0/1 polytopes with high semidefinite extension complexitySebastian Pokutta, Georgia Institute of Technology11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space
4:00 - 4:45Semidefinite programming and discrepancy- Recent developmentsNikhil Bansal, Technische Universiteit Eindhoven11th Floor Lecture Hall
PDF
PDF

WednesdayFebruary 12, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45TBAMichel Goemans, Massachusetts Institute of Technology11th Floor Lecture Hall
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Semidefinite programming bounds for codes and anticodes in Cayley graphsFrank Vallentin, Universitat zu Koln11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Near optimal deterministic volume estimation via M-ellipsoidsDaniel Dadush, New York University11th Floor Lecture Hall
PDF
12:30 - 12:40Group Photo11th Floor Lecture Hall
12:40 - 2:30Break for Lunch
2:30 - 3:15A Non-Convex Optimization Approach to Network Localization- Polynomial-Time Computability and Rigidity-Theoretic ImplicationsAnthony Man-Cho So, Chinese University of Hong Kong11th Floor Lecture Hall
PDF
PDF
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 Break11th Floor Collaborative Space
4:00 - 4:45Graph parameters from entangled games and quantum zero-error communication.Jop Briet, New York University11th Floor Lecture Hall
7:00 - 8:30Poster Session and Dessert Reception11th Floor Lecture Hall and Collaborative Space

ThursdayFebruary 13, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Three-dimensional Structure Determination of Molecules without Crystallization- from Electron Microscopy to Semidefinite ProgrammingAmit Singer, Princeton University11th Floor Lecture Hall
PDF
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15On the power of Symmetric SDP relaxationsPrasad Raghavendra, University of California, Berkeley11th Floor Lecture Hall
PDF
11:30 - 12:15Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphsYuan Zhou, Carnegie Mellon University11th Floor Lecture Hall
12:30 - 2:30Break for Lunch
2:30 - 3:15SDP and eigenvalue bounds for the graph partition problemRenata Sotirov, Tilburg University, Netherlands11th Floor Lecture Hall
PDF
PDF
3:25 - 3:25Please take a moment to complete the survey that was distributed by email.
3:30 - 4:00Coffee Break11th Floor Collaborative Space
4:00 - 4:45TBAPablo Parrilo, Massachusetts Institute of Technology11th Floor Lecture Hall

FridayFebruary 14, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Faster SDP hierarchy solvers for local rounding algorithmsAli Kemal Sinop, IAS11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Latent Variable Graphical Model Selection via Convex OptimizationVenkat Chandrasekaran, California Institute of Technology11th Floor Lecture Hall
11:30 - 12:15The Matrix Multiplicative Weights Algorithm- Applications to SDP and Online Matrix PredictionSatyen Kale, Yahoo!11th Floor Lecture Hall
PDF
PDF
12:30 - 2:30Break for Lunch
1:00 - 2:15Theory Seminar -ongoing semester seminar- Improving Christofides' Algorithm for the s-t Path Traveling Salesman ProblemDavid Shmoys, Cornell University11th Floor Classroom
PDF
2:30 - 3:30Learning how to rank via forbidden patterns - semirankings and the Erdos-Hajnal ConjectureKrzysztof Choromanski, Google Inc.11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayFebruary 17, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayFebruary 18, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:30Professional Development: Ethics 111th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayFebruary 19, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayFebruary 20, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayFebruary 21, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:00 - 2:15Theory Seminar- Beyond Locality-Sensitive HashingIlya Razenshteyn, MIT11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayFebruary 24, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayFebruary 25, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:30Professional Development: Ethics 211th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayFebruary 26, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
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 Break11th Floor Collaborative Space
4:15 - 5:30Interlacing Families and Kadison--SingerAdam Marcus, Crisply LLC and Yale University11th Floor Lecture Hall

ThursdayFebruary 27, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayFebruary 28, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:00 - 2:15Theory Seminar11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayMarch 3, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayMarch 4, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
2:30 - 3:30Efficiently inferring community structure in bipartite networksDaniel Larremore, Harvard School of Public Health11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayMarch 5, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
12:00 - 1:00Research LunchPlease 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:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayMarch 6, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayMarch 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:00 - 2:15Theory Seminar - The Simple Economics of Approximately Optimal AuctionsJason Hartline, Northwestern University and Harvard University11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayMarch 10, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:00 - 4:15Maximum Entropy Summary TreesHoward Karloff, Yahoo! Inc.11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayMarch 11, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
2:30 - 3:30Flows in 1-crossing-minor-free graphsErin Chambers, St. Louis University11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayMarch 12, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
2:45 - 3:00Long Term Visitor Group Photo11th Floor Lecture Hall
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayMarch 13, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
2:30 - 3:30Weekly ICERM Seminar- Subgraphs in Random GraphsAmanda Redlich, Bowdoin College10th Floor Classroom
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayMarch 14, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:00 - 2:15Theory Seminar- Bandits with KnapsacksAlex Slivkins, Microsoft Research, NYC10th Floor Classroom
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

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
PDF
PDF
11:00 - 11:45Fast Testing of Graph PropertiesArtur Czumaj, University of Warwick11th Floor Lecture Hall
PDF
12:00 - 1:45Break for Lunch
1:45 - 2:30New Online Algorithms for Story Scheduling in Web AdvertisingSusanne Albers, TU Munich11th Floor Lecture Hall
PDF
PDF
2:45 - 3:30Trace Complexity of Network ReconstructionFlavio Chierichetti, Sapienza University of Rome11th Floor Lecture Hall
PDF
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
PDF
PDF
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
PDF
11:00 - 11:45Algorithms on Evolving Data SetsMohammad Mahdian, Google INC11th Floor Lecture Hall
PDF
PDF
12:00 - 1:45Break for Lunch
1:45 - 2:30Computing Stationary Distribution, LocallyDevavrat Shah, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
2:45 - 3:30Reconstructing Latent Similarities in a Multiplex Social NetworkAlex Slivkins, Microsoft Research11th Floor Lecture Hall
PDF
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
PDF
PDF

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
PDF
PDF
11:00 - 11:45Peeling AlgorithmsMichael Mitzenmacher, Harvard University11th Floor Lecture Hall
PDF
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
PDF
2:45 - 3:30Power Law ComplexityPiotr Sankowski, University of Warsaw11th Floor Lecture Hall
PDF
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
PDF
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
PDF
2:45 - 3:30Online Stochastic Matching- New Results and Open ProblemsVahab Mirrokni, Google Inc.11th Floor Lecture Hall
PDF
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
PDF
PDF

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
PDF
11:00 - 11:45Estimating Network ParametersRavi Kumar, Google Inc.11th Floor Lecture Hall
PDF
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
PDF
2:45 - 3:30An Efficient reconciliation algorithm for social networksSilvio Lattanzi, Google Inc.11th Floor Lecture Hall
PDF
PDF
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
PDF

MondayMarch 24, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayMarch 25, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayMarch 26, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayMarch 27, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayMarch 28, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayMarch 31, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayApril 1, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayApril 2, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayApril 3, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayApril 4, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:00 - 2:00Theory Seminar-Superlinear Lower Bounds for Multipass Graph ProcessingVenkatesan Guruswami, Carnegie-Mellon University11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayApril 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 8:55Registration: Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond Workshop11th Floor Collaborative Space
8:55 - 9:00WelcomeICERM Director11th Floor Lecture Hall
9:00 - 9:45Efficient Solvers for Linear Systems in Graph LaplaciansRichard Peng, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Electrical Flows, Continuous Optimization, and the Maximum Flow ProblemAleksander Madry, Ecole Polytechnique Federale De Lausanne11th Floor Lecture Hall
PDF
11:30 - 12:15Small Lifts of Expander Graphs are ExpandingAlexandra Kolla, Univeristy of Illinois at Urbana-Champaign11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15An L^p Theory of Sparse Graph LimitsChristian Borgs, Microsoft Research11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45The Power of Locality for Network AlgorithmsJennifer Chayes, Microsoft Research11th Floor Lecture Hall
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayApril 8, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Random Walks as a Stable Analogue of Eigenvectors with Applications to Nearly-Linear-Time Graph PartitioningLorenzo Orecchia, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Graph SparsificationDebmalya Panigrahi, Duke University11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Heat Kernel Pagerank as a Linear Solver and Applications to Consensus ProblemsOlivia Simpson, University of California, San Diego11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15Computations on Graph LaplaciansErik Boman, Sandia National Laboratories11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Poster Session PreviewMichela 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

WednesdayApril 9, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45A simple parallel algorithm for spectral graph sparsificationYiannis Koutis, University of Puerto Rico11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15A Simple, Electrical, Gradient Descent Algorithm for Approximate Max FlowNikhil Srivastava, Microsoft Research India11th Floor Lecture Hall
PDF
11:30 - 12:15Guaranteed Tensor Decomposition through Alternating Rank-1 UpdatesAnima Anandkumar, University of California, Irvine11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15Faster Algorithms via Approximation TheoryNisheeth Vishnoi, Microsoft Research India11th Floor Lecture Hall
PDF
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:45Approximate Spectral Clustering via Randomized SketchingChristos Boutsidis, Yahoo! Labs, New York11th Floor Lecture Hall
PDF
PDF

ThursdayApril 10, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45A simple algorithm for finding clusters in a random environmentVan Vu, Yale University11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Anti-differentiating approximation alogrithms for min-cuts and new relationships between Page Rank, spectral, and localized flowDavid Gleich, Purdue University11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Spectral partitioning and higher-order Cheeger inequalitiesJames Lee, University of Washington11th Floor Lecture Hall
PDF
12:30 - 12:45Group Photo11th Floor Lecture Hall
12:45 - 2:30Break for Lunch
2:30 - 3:15Improved Cheeger's InequalityShayan Oveis-Gharan, Stanford University11th Floor Lecture Hall
PDF
3:30 - 3:30Please take a moment to complete the survey that was distributed by email.
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Open Problems Session11th Floor Lecture Hall

FridayApril 11, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Faster Subset Selection for Matrices and ApplicationsHaim Avron, IBM Corporation11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Large-scale Computations of Edge-Importance MeasuresEvimaria Terzi, Boston University11th Floor Lecture Hall
PDF
11:30 - 12:15TBAJohn Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall
12:30 - 2:30Break for Lunch
2:30 - 3:15Open Problems for Real Data11th Floor Lecture Hall
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45TBATBA11th Floor Lecture Hall

MondayApril 14, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayApril 15, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayApril 16, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayApril 17, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayApril 18, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:30Coffee/Tea Break11th Floor Collaborative Space
9:30 - 10:15Local computation algorithms for sparse graphsRonitt Rubinfeld, Massachusetts Institute of Technology11th Floor Lecture Hall
10:30 - 10:55Approximating matching size from random streamsMichael Kapralov, Massachusetts Institute of Technology11th Floor Lecture Hall
11:00 - 11:25Turnstile Streaming Algorithms Might as Well Be Linear SketchesHuy Le Nguyen, Princeton University11th Floor Lecture Hall
1:00 - 1:45Testing and Reconstruction of Lipschitz FunctionsSofya Raskhodnikova, Pennsylvania State University and Boston University11th Floor Lecture Hall
2:00 - 2:45Analyzing Big Graphs via Sketching and StreamingAndrew McGregor, University of Massachusetts, Amherst11th Floor Lecture Hall
3:00 - 3:45Streaming Interactive Proofs or: How I Learned to Stop Worrying and Trust the CloudAmit Chakrabarti, Dartmouth College11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayApril 21, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayApril 22, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayApril 23, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayApril 24, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayApril 25, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:00 - 2:00Storage and Search in Dynamic Peer-to-Peer NetworksJohn Augustine, IIT Madras11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayApril 28, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

TuesdayApril 29, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

WednesdayApril 30, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:00 - 5:20Optimization Algorithms for Planar Graphs (ongoing semester course)Phil Klein, Brown University and Claire Mathieu, Brown University11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

ThursdayMay 1, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
3:30 - 4:00Coffee Break11th Floor Collaborative Space

FridayMay 2, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
1:00 - 2:15New Algorithms for Representation Learning and BeyondAnkur Moitra, MIT11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space

MondayMay 5, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 8:55Registration11th Floor Collaborative Space
8:55 - 9:00WelcomeICERM Director11th Floor Lecture Hall
9:00 - 9:45Eigenvectors, Heat Kernels, and Low Dimensional Representation of Data SetsPeter Jones, Yale University11th Floor Lecture Hall
PDF
PDF
9:50 - 10:35Multiscale Geometric Methods for Statistical Learning and Data in High-DimensionaMauro Maggioni, Duke University11th Floor Lecture Hall
PDF
10:40 - 11:10Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Tracking Influences within Dynamic NetworksRebecca Willett, University of Wisconsin11th Floor Lecture Hall
PDF
12:00 - 2:00Lunch Break and Free Time
2:00 - 2:45Robust and Fast Subspace RecoveryGilad Lerman, University of Minnesota11th Floor Lecture Hall
PDF
2:50 - 3:35TBARoy Lederman, Yale University11th Floor Lecture Hall
3:40 - 4:10Coffee Break11th Floor Collaborative Space
4:10 - 4:55Diffuse Scattering on Graphs and Combinatorial Inverse ProblemsAnna Gilbert, University of Michigan11th Floor Lecture Hall
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayMay 6, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Covariance Matrix Estimation for the Cryo-EM Heterogeneity ProblemAmit Singer, Princeton University11th Floor Lecture Hall
PDF
9:50 - 10:35A randomized approximate nearest neighbors algorithmAndrei Osipov, Yale University11th Floor Lecture Hall
PDF
10:40 - 11:10Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Eigenvector localization, implicit regularization, and algorithmic anti-differentiation for large-scale graphs and networked dataMichael W. Mahoney, University of California, Berkeley11th Floor Lecture Hall
PDF
PDF
12:00 - 2:00Lunch Break and Free Time
2:00 - 2:45TBAVladimir Rokhlin, Yale University11th Floor Lecture Hall
2:50 - 3:35Gaps in eigenfunctions of GraphsFan Chung, University of California, San Diego11th Floor Lecture Hall
PDF
3:40 - 4:10Coffee Break11th Floor Collaborative Space
4:10 - 4:55Inverse problems on random graphs and censored block modelsEmmanuel Abbe, Princeton University11th Floor Lecture Hall

WednesdayMay 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45New Algorithms for Learning Incoherent and Overcomplete DictionariesRong Ge, Microsoft Research11th Floor Lecture Hall
PDF
PDF
9:50 - 10:35A threshold for reconstruction in stochastic block modelsJoe Neeman, University of Texas at Austin11th Floor Lecture Hall
PDF
10:40 - 11:10Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Network Clustering, the Block Stochastic Model, and a Regular GraphIoana Dumitriu, University of Washington11th Floor Lecture Hall
PDF
12:00 - 12:05Group Photo11th Floor Lecture Hall
12:05 - 2:00Lunch Break and Free Time
2:00 - 2:45Dimension reduction in the l1 norm- When and how is it possibleRachel Ward, University of Texas at Austin11th Floor Lecture Hall
PDF
2:50 - 3:35Random weighted projections, random quadratic forms and random eigenvectorsKe Wang, University of Minnesota11th Floor Lecture Hall
PDF
3:40 - 4:10Coffee Break11th Floor Collaborative Space
4:10 - 4:55Spectral algorithms for graph mining and analysisYiannis Koutis, University of Puerto Rico11th Floor Lecture Hall
PDF
7:00 - 8:30Poster Session and Dessert Reception11th Floor Collaborative Space

ThursdayMay 8, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Information-theoretic learned linear projections for dimensionality reductionLawrence Carin, Duke University11th Floor Lecture Hall
PDF
9:50 - 10:35A Polynomial Time Algorithm for Lossy Population RecoveryAnkur Moitra, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
10:40 - 11:10Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Permanent estimators via random matricesMark Rudelson, Univeristy of Michigan11th Floor Lecture Hall
PDF
PDF
12:00 - 2:00Lunch Break and Free Time
2:00 - 2:45A simple spectral algorithm for a general clustering problemVan Vu, Yale University11th Floor Lecture Hall
PDF
2:50 - 3:35Random perturbation of low rank matrices- Improving classical boundsSean O'Rourke, Yale University11th Floor Lecture Hall
PDF
3:40 - 4:10Coffee Break11th Floor Collaborative Space
4:10 - 4:55Is Belief Propagation a Spectral algorithmElchanan Mossel, University of California, Berkeley11th Floor Lecture Hall
PDF

FridayMay 9, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:50 - 10:35Panel SummaryPanel Discussion Chair: Anna Gilbert, University of Michigan11th Floor Lecture Hall
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Panel Summary11th Floor Lecture Hall
12:00 - 5:00Afternoon Free for Collaborations


TuesdayFebruary 4, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:15 - 9:30Welcome11th Floor Lecture Hall
9:30 - 10:30The geometry of unweighted k-nearest neighbor graphs- first results and many questionsUlrike von Luxbourg, Universitat Hamburg11th Floor Lecture Hall
10:30 - 11:30From partial differential equations to graphs- curvature and clustersYves van Gennip, University of Nottingham11th Floor Lecture Hall
PDF
PDF
11:30 - 1:00Break for Lunch
1:00 - 1:30Distance geometry on graphs via synchronizationMihai Cucuringu, UCLA11th Floor Lecture Hall
PDF
1:30 - 2:00TBAMichaela Puck Rombach, UCLA11th Floor Lecture Hall
2:00 - 2:15Break11th Floor Collaborative Space
2:15 - 3:15Applied Harmonic Analysis meets Compressed SensingGitta Kutyniok, TU Berlin11th Floor Lecture Hall
PDF
PDF
4:45 - 5:45Poster Session11th Floor Collaborative Space

WednesdayFebruary 5, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
10:00 - 11:00Scalable Gaussian process models on matrices and tensorsYuan Qi, Purdue University11th Floor Lecture Hall
PDF
11:00 - 11:30Break11th Floor Collaborative Space
11:30 - 12:00Spectral Methods for Analyzing Large DataBlake Hunter, UCLA11th Floor Lecture Hall
PDF
12:00 - 12:30Minimal Dirichlet energy partitions for graphsChris White, University of Texas at Austin11th Floor Lecture Hall
PDF
PDF

ThursdayFebruary 6, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
10:00 - 11:00Proximal splitting algorithms for two class and multiclass total variation clusteringThomas Laurent, Loyola Marymount University11th Floor Lecture Hall
PDF
PDF
11:00 - 12:00Pooling fidelity and phase recoveryArthur Szlam, City College, CUNY11th Floor Lecture Hall
PDF

FridayFebruary 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:00Random Graph Models for Image PatchesFrancois Meyer, University of Colorado at Boulder11th Floor Lecture Hall
PDF
PDF
11:00 - 11:30Break11th Floor Collaborative Space
11:30 - 12:00Non-local Beltrami and Beltrami on graphDominique Zosso, UCLA11th Floor Lecture Hall
PDF
1:30 - 2:30Graph cut, convex relaxation and continuous max-flow problemsTai Xue-Cheng, University of Bergen10th Floor Classroom
PDF

ThursdayApril 24, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 9:00Registration11th Floor Collaborative Space
9:00 - 10:20Basic techniques of fixed-parameter tractability (Part 1)Saket Saurabh, Institute of Mathematical Sciences11th Floor Lecture Hall
PDF
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:00 - 12:30Basic techniques of fixed-parameter tractability (Part 2)Daniel Lokshtanov, University of Bergen11th Floor Lecture Hall
PDF
12:30 - 2:00Break for Lunch
2:00 - 3:30KernelizationSaket Saurabh, Institute of Mathematical Sciences11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research

FridayApril 25, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:20Treewidth and applicationsFedor Fomin, University of Bergen11th Floor Lecture Hall
PDF
10:30 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 11:15Open Problem Session11th Floor Lecture Hall
11:15 - 12:45Minors and AlgorithmsErik Demaine, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
12:45 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research

SaturdayApril 26, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:20Approximation AlgorithmsMohammad Taghi Hajiaghayi, University of Maryland11th Floor Lecture Hall
PDF
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:00 - 12:30Lower boundsDaniel Marx, Hungarian Academy of Sciences (MTA)11th Floor Lecture Hall
PDF
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research

SundayApril 27, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:20SeparatorsDaniel Marx, Hungarian Academy of Sciences (MTA)11th Floor Lecture Hall
PDF
10:30 - 11:00Coffee/Tea Break
11:00 - 12:30Connecting to the Real-World ApplicationsBlair Sullivan, North Carolina State University11th Floor Lecture Hall
PDF
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break
4:00 - 5:00Research

MondayApril 28, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Opening Session11th Floor Lecture Hall
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Lecture Hall
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research
5:00 - 5:30Problem Session Update11th Floor Lecture Hall

TuesdayApril 29, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Research
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Lecture Hall
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research
5:00 - 5:30Problem Session Update11th Floor Lecture Hall

WednesdayApril 30, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Research
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Lecture Hall
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research
5:00 - 5:30Problem Session Update10th floor classroom

ThursdayMay 1, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Research
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Lecture Hall
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research
5:00 - 5:30Problem Session Update11th Floor Lecture Hall

FridayMay 2, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Research
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Collaborative Space
12:30 - 2:30Break for Lunch
2:30 - 5:00Closing Session/Wrap-Up11th Floor Lecture Hall


Workshops and Associated Events:

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.

  • Amir Ali Ahmadi
    (Massachusetts Institute of Technology)
  • Ian Alevy
    (Brown University)
  • Sanjeev Arora *
    (Princeton University)
  • Chen Avin
    (Ben Gurion University of the Negev)
  • Nikhil Bansal *
    (Technische Universiteit Eindhoven)
  • Boaz Barak *
    (Microsoft Research)
  • Emanuel Ben-David
    (Columbia University)
  • Ioana Bercea
    (University of Maryland)
  • Tejal Bhamre
    (Princeton University)
  • Milan Bradonjic
    (Lucent Technologies Bell Laboratories)
  • Xavier Bresson
    (Université de Lausanne)
  • Jop Briët*
    (New York University)
  • Venkat Chandrasekeran*
    (California Institute of Technology)
  • Krzysztof Choromanski *
    (Google Inc.)
  • Mihai Cucuringu
    (University of California, Los Angeles)
  • Daniel Dadush*
    (New York University)
  • Lorenzo De Stefani
    (Università di Padova)
  • Thomas Dickerson
    (Brown University)
  • Hamza Fawzi
    (Massachusetts Institute of Technology)
  • Arjuna Flenner
    (Naval Air Warfare Center)
  • Kyle Fox
    (University of Illinois at Urbana-Champaign)
  • Eli Fox-Epstein
    (Brown University)
  • Nathanaël François
    (Université de Paris VII (Denis Diderot))
  • Cristina Garcia
    (Claremont Graduate University)
  • Nicolas Garcia
    (Carnegie Mellon University)
  • Michel Goemans *
    (Massachusetts Institute of Technology)
  • Sebastian Gruler
    (Universität Konstanz)
  • Steven Heilman
    (Courant Institute of Mathematical Sciences)
  • Huiyi Hu
    (University of California, Los Angeles)
  • Blake Hunter
    (University of California, Los Angeles)
  • Sameer Iyer
    (Brown University)
  • Satyen Kale *
    (Yahoo! Inc.)
MondayFebruary 10, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 8:55Registration: Semidefinite Programming and Graph Algorithms Workshop11th Floor Collaborative Space
8:55 - 9:00WelcomeICERM Director11th Floor Lecture Hall
9:00 - 9:45The Moment-LP and Moment-SOS approaches in polynomial optimizationJean Lasserre, Centre National de la Recherche Scientifique (CNRS)11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Rounding Sum of Squares RelaxationsBoaz Barak, Microsoft Research11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15TBAJonathan Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall
12:30 - 2:30Break for Lunch
2:30 - 3:15Convergence of SDP hierarchies using kernel based methodsStephanie Wehner, National University of Singapore11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break10th Floor Collaborative Space
4:00 - 4:45Vertical versus horizontal Poincare inequalitiesAssaf Naor, New York University11th Floor Lecture Hall
PDF
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayFebruary 11, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Expander flows, Geometric embeddings and Graph PartitioningClaire Mathieu, Ecole Normale Superieure11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Towards a Better Approximation of Sparsest Cut?Sanjeev Arora, Princeton University11th Floor Lecture Hall
PDF
11:30 - 12:15Going off the gridBenjamin Recht, University of California, Berkeley11th Floor Lecture Hall
PDF
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15On the existence of 0/1 polytopes with high semidefinite extension complexitySebastian Pokutta, Georgia Institute of Technology11th Floor Lecture Hall
3:30 - 4:00Coffee Break11th Floor Collaborative Space
4:00 - 4:45Semidefinite programming and discrepancy- Recent developmentsNikhil Bansal, Technische Universiteit Eindhoven11th Floor Lecture Hall
PDF
PDF

WednesdayFebruary 12, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45TBAMichel Goemans, Massachusetts Institute of Technology11th Floor Lecture Hall
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Semidefinite programming bounds for codes and anticodes in Cayley graphsFrank Vallentin, Universitat zu Koln11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Near optimal deterministic volume estimation via M-ellipsoidsDaniel Dadush, New York University11th Floor Lecture Hall
PDF
12:30 - 12:40Group Photo11th Floor Lecture Hall
12:40 - 2:30Break for Lunch
2:30 - 3:15A Non-Convex Optimization Approach to Network Localization- Polynomial-Time Computability and Rigidity-Theoretic ImplicationsAnthony Man-Cho So, Chinese University of Hong Kong11th Floor Lecture Hall
PDF
PDF
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 Break11th Floor Collaborative Space
4:00 - 4:45Graph parameters from entangled games and quantum zero-error communication.Jop Briet, New York University11th Floor Lecture Hall
7:00 - 8:30Poster Session and Dessert Reception11th Floor Lecture Hall and Collaborative Space

ThursdayFebruary 13, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Three-dimensional Structure Determination of Molecules without Crystallization- from Electron Microscopy to Semidefinite ProgrammingAmit Singer, Princeton University11th Floor Lecture Hall
PDF
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15On the power of Symmetric SDP relaxationsPrasad Raghavendra, University of California, Berkeley11th Floor Lecture Hall
PDF
11:30 - 12:15Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphsYuan Zhou, Carnegie Mellon University11th Floor Lecture Hall
12:30 - 2:30Break for Lunch
2:30 - 3:15SDP and eigenvalue bounds for the graph partition problemRenata Sotirov, Tilburg University, Netherlands11th Floor Lecture Hall
PDF
PDF
3:25 - 3:25Please take a moment to complete the survey that was distributed by email.
3:30 - 4:00Coffee Break11th Floor Collaborative Space
4:00 - 4:45TBAPablo Parrilo, Massachusetts Institute of Technology11th Floor Lecture Hall

FridayFebruary 14, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Faster SDP hierarchy solvers for local rounding algorithmsAli Kemal Sinop, IAS11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee Break11th Floor Collaborative Space
10:30 - 11:15Latent Variable Graphical Model Selection via Convex OptimizationVenkat Chandrasekaran, California Institute of Technology11th Floor Lecture Hall
11:30 - 12:15The Matrix Multiplicative Weights Algorithm- Applications to SDP and Online Matrix PredictionSatyen Kale, Yahoo!11th Floor Lecture Hall
PDF
PDF
12:30 - 2:30Break for Lunch
1:00 - 2:15Theory Seminar -ongoing semester seminar- Improving Christofides' Algorithm for the s-t Path Traveling Salesman ProblemDavid Shmoys, Cornell University11th Floor Classroom
PDF
2:30 - 3:30Learning how to rank via forbidden patterns - semirankings and the Erdos-Hajnal ConjectureKrzysztof Choromanski, Google Inc.11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee Break11th 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.

  • 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
PDF
PDF
11:00 - 11:45Fast Testing of Graph PropertiesArtur Czumaj, University of Warwick11th Floor Lecture Hall
PDF
12:00 - 1:45Break for Lunch
1:45 - 2:30New Online Algorithms for Story Scheduling in Web AdvertisingSusanne Albers, TU Munich11th Floor Lecture Hall
PDF
PDF
2:45 - 3:30Trace Complexity of Network ReconstructionFlavio Chierichetti, Sapienza University of Rome11th Floor Lecture Hall
PDF
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
PDF
PDF
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
PDF
11:00 - 11:45Algorithms on Evolving Data SetsMohammad Mahdian, Google INC11th Floor Lecture Hall
PDF
PDF
12:00 - 1:45Break for Lunch
1:45 - 2:30Computing Stationary Distribution, LocallyDevavrat Shah, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
2:45 - 3:30Reconstructing Latent Similarities in a Multiplex Social NetworkAlex Slivkins, Microsoft Research11th Floor Lecture Hall
PDF
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
PDF
PDF

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
PDF
PDF
11:00 - 11:45Peeling AlgorithmsMichael Mitzenmacher, Harvard University11th Floor Lecture Hall
PDF
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
PDF
2:45 - 3:30Power Law ComplexityPiotr Sankowski, University of Warsaw11th Floor Lecture Hall
PDF
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
PDF
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
PDF
2:45 - 3:30Online Stochastic Matching- New Results and Open ProblemsVahab Mirrokni, Google Inc.11th Floor Lecture Hall
PDF
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
PDF
PDF

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
PDF
11:00 - 11:45Estimating Network ParametersRavi Kumar, Google Inc.11th Floor Lecture Hall
PDF
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
PDF
2:45 - 3:30An Efficient reconciliation algorithm for social networksSilvio Lattanzi, Google Inc.11th Floor Lecture Hall
PDF
PDF
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
PDF


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.

  • Rediet Abebe
    (University of Cambridge)
  • Monther Alfuraidan
    (King Fahd University of Petroleum and Minerals)
  • Zeyuan Allen-Zhu
    (Massachusetts Institute of Technology)
  • Anima Anandkumar*
    (University of California, Irvine)
  • John Augustine
    (Indian Institute of Technology)
  • Chen Avin
    (Ben Gurion University of the Negev)
  • Haim Avron*
    (IBM Corporation)
  • Frank Bauer
    (Harvard University)
  • Petra Berenbrink
    (Simon Fraser University)
  • Daniel Bienstock
    (Columbia University)
  • Erik Boman*
    (Sandia National Laboratories)
  • Christian Borgs *
    (Microsoft Research)
  • Christos Boutsidis*
    (Yahoo! Inc.)
  • Yixin Cao
    (Hungarian Academy of Sciences (MTA))
  • Jennifer Chayes *
    (Microsoft Research)
  • Michael Cohen
    (Massachusetts Institute of Technology)
  • Mihai Cucuringu
    (University of California, Los Angeles)
  • Thomas Dickerson
    (Brown University)
  • Michela Egidi
    (Durham University)
  • Lledó Esquerra-Ortells
    (University of Colorado)
  • Pedro Felzenszwalb
    (Brown University)
  • Kyle Fox
    (University of Illinois at Urbana-Champaign)
  • Eli Fox-Epstein
    (Brown University)
  • Nathanaël François
    (Université de Paris VII (Denis Diderot))
  • David Gillman
    (New College of Florida)
  • David Gleich*
    (Purdue University)
  • Mamikon Gulian
    (Brown University)
  • Bruce Hendrickson
    (Sandia National Laboratories)
  • Emilie Hogan
    (Pacific Northwest National Laboratory)
  • Majid Janzamin
    (University of California, Irvine)
  • Jonathan Kelner *
    (Massachusetts Institute of Technology)
  • Yvonne Kemper
    (National Institute of Standards and Technology)
  • Franklin Kenter
    (Rice University)
  • Richard Kenyon
    (Brown University)
  • Philip Klein
    (Brown University)
  • Caroline Klivans
    (Brown University)
  • Alexandra Kolla*
    (University of Illinois at Urbana-Champaign)
  • Yiannis Koutis *
    (University of Puerto Rico)
  • Rasmus Kyng
    (Yale University)
  • Matthew Langston
    (Reservoir Labs Inc)
  • James Lee*
    (University of Washington)
  • Gabor Lippner
    (Harvard University)
  • Shiping Liu
    (University of Durham)
  • Aleksander Madry*
    (École Polytechnique Fédérale de Lausanne (EPFL))
  • Ahmad Mahmoody
    (Brown University)
  • William Martin
    (Worcester Polytechnic Institute)
  • Claire Mathieu
    (École Normale Supérieure)
  • Charalampos Mavroforakis
    (Boston University)
  • Patrick McDonald
    (New College of Florida)
  • David Meierfrankenfeld
    (Brown University)
  • Francois Meyer
    (University of Colorado)
  • Gary Miller
    (Carnegie Mellon University)
  • Sobhan Naderi Parizi
    (Brown University)
  • Krishna Nand
    (Brown University)
  • Danupon Nanongkai
    (Nanyang Technological University)
  • Lorenzo Orecchia*
    (Massachusetts Institute of Technology)
  • Shayan Oveis-Gharan*
    (Stanford University)
  • Jakub Pachocki
    (Carnegie Mellon University)
  • Gopal Pandurangan
    (Nanyang Technological University)
  • Debmalya Panigrahi *
    (Duke University)
  • Richard Peng*
    (Massachusetts Institute of Technology)
  • Lam Pham
    (Yale University)
  • Mason Porter
    (University of Oxford)
  • Saad Quader
    (University of Connecticut)
  • Sanjay Ramassamy
    (Brown University)
  • Anup Rao
    (Yale University)
  • Ben Raphael
    (Brown University)
  • Amanda Redlich
    (Bowdoin College)
  • Igor Rivin
    (Temple University)
  • Scott Roche
    (Northeastern University)
  • Sushant Sachdeva
    (Yale University)
  • Bernd Schroeder
    (Louisiana Tech University)
  • Oliva Simpson*
    (University of California, San Diego)
  • Ali Sinop
    (Institute for Advanced Study)
  • Jon Sjogren
    (Towson State University)
  • Nikhil Srivastava*
    (Microsoft Research India)
  • He Sun
    (Max-Planck-Institut für Informatik)
  • Christino Tamon
    (Clarkson University)
  • Evimaria Terzi*
    (Boston University)
  • Charalampos Tsourakakis
    (Carnegie Mellon University)
  • Lara Ruth Turner
    (University of Vienna )
  • Eli Upfal
    (Brown University)
  • Nisheeth Vishnoi*
    (Microsoft Research India)
  • Van Vu*
    (Yale University)
  • Shen Chen Xu
    (Carnegie Mellon University)
  • Grigory Yaroslavtsev
    (Pennsylvania State University)
  • Neal Young
    (University of California, Riverside)
  • Luca Zanetti
    (Universität des Saarlandes)
  • Hang Zhou
    (École Normale Supérieure)
  • Yao Zhu
    (Purdue University)
MondayApril 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 8:55Registration: Electrical Flows, Graph Laplacians, and Algorithms: Spectral Graph Theory and Beyond Workshop11th Floor Collaborative Space
8:55 - 9:00WelcomeICERM Director11th Floor Lecture Hall
9:00 - 9:45Efficient Solvers for Linear Systems in Graph LaplaciansRichard Peng, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Electrical Flows, Continuous Optimization, and the Maximum Flow ProblemAleksander Madry, Ecole Polytechnique Federale De Lausanne11th Floor Lecture Hall
PDF
11:30 - 12:15Small Lifts of Expander Graphs are ExpandingAlexandra Kolla, Univeristy of Illinois at Urbana-Champaign11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15An L^p Theory of Sparse Graph LimitsChristian Borgs, Microsoft Research11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45The Power of Locality for Network AlgorithmsJennifer Chayes, Microsoft Research11th Floor Lecture Hall
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayApril 8, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Random Walks as a Stable Analogue of Eigenvectors with Applications to Nearly-Linear-Time Graph PartitioningLorenzo Orecchia, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Graph SparsificationDebmalya Panigrahi, Duke University11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Heat Kernel Pagerank as a Linear Solver and Applications to Consensus ProblemsOlivia Simpson, University of California, San Diego11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15Computations on Graph LaplaciansErik Boman, Sandia National Laboratories11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Poster Session PreviewMichela 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

WednesdayApril 9, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45A simple parallel algorithm for spectral graph sparsificationYiannis Koutis, University of Puerto Rico11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15A Simple, Electrical, Gradient Descent Algorithm for Approximate Max FlowNikhil Srivastava, Microsoft Research India11th Floor Lecture Hall
PDF
11:30 - 12:15Guaranteed Tensor Decomposition through Alternating Rank-1 UpdatesAnima Anandkumar, University of California, Irvine11th Floor Lecture Hall
PDF
12:30 - 2:30Break for Lunch
2:30 - 3:15Faster Algorithms via Approximation TheoryNisheeth Vishnoi, Microsoft Research India11th Floor Lecture Hall
PDF
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:45Approximate Spectral Clustering via Randomized SketchingChristos Boutsidis, Yahoo! Labs, New York11th Floor Lecture Hall
PDF
PDF

ThursdayApril 10, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45A simple algorithm for finding clusters in a random environmentVan Vu, Yale University11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Anti-differentiating approximation alogrithms for min-cuts and new relationships between Page Rank, spectral, and localized flowDavid Gleich, Purdue University11th Floor Lecture Hall
PDF
PDF
11:30 - 12:15Spectral partitioning and higher-order Cheeger inequalitiesJames Lee, University of Washington11th Floor Lecture Hall
PDF
12:30 - 12:45Group Photo11th Floor Lecture Hall
12:45 - 2:30Break for Lunch
2:30 - 3:15Improved Cheeger's InequalityShayan Oveis-Gharan, Stanford University11th Floor Lecture Hall
PDF
3:30 - 3:30Please take a moment to complete the survey that was distributed by email.
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45Open Problems Session11th Floor Lecture Hall

FridayApril 11, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Faster Subset Selection for Matrices and ApplicationsHaim Avron, IBM Corporation11th Floor Lecture Hall
PDF
10:00 - 10:30Coffee/Tea Break11th Floor Collaborative Space
10:30 - 11:15Large-scale Computations of Edge-Importance MeasuresEvimaria Terzi, Boston University11th Floor Lecture Hall
PDF
11:30 - 12:15TBAJohn Kelner, Massachusetts Institute of Technology11th Floor Lecture Hall
12:30 - 2:30Break for Lunch
2:30 - 3:15Open Problems for Real Data11th Floor Lecture Hall
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 4:45TBATBA11th Floor Lecture Hall


Eigenvectors in graph theory and related problems in numerical linear algebra
(May 5 - 9, 2014)


CLICK HERE TO PARTICIPATE
Review of applications will begin on December 15, 2013
Organizing Committee

 

Patent(s) Pending & Copyright © Lumeta Corporation 2000-2013. All Rights Reserved. LUMETA, LUMETA Logo, IPSONAR and the IPSONAR logo are the trademarks and service marks of Lumeta Corporation.
Description

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.


  • Emmanuel Abbe *
    (Princeton University)
  • Derek Aguiar
    (Brown University)
  • John Augustine
    (Indian Institute of Technology)
  • Chen Avin
    (Ben Gurion University of the Negev)
  • Guillaume Basse
    (Harvard University)
  • Devasis Bassu
    (Applied Communication Sciences)
  • Daniel Bienstock
    (Columbia University)
  • Milan Bradonjic
    (Bell Labs, Alcatel-Lucent)
  • Lawrence Carin *
    (Duke University)
  • Yanlai Chen
    (University of Massachusetts)
  • Peter Chin
    (Boston University)
  • Fan Chung Graham*
    (University of California, San Diego)
  • Thomas Dickerson
    (Brown University)
  • Ioana Dumitriu*
    (University of Washington)
  • Kyle Fox
    (University of Illinois at Urbana-Champaign)
  • Eli Fox-Epstein
    (Brown University)
  • Nathanaël François
    (Université de Paris VII (Denis Diderot))
  • Cameron Freer
    (Massachusetts Institute of Technology)
  • Paolo Gatto
    (Brown University)
  • Rong Ge *
    (Microsoft Research)
  • Anna Gilbert *
    (University of Michigan)
  • Venu Gopal
    (Brown University)
  • David Guarrera
    (QS2/DARPA)
  • Steven Heilman
    (Courant Institute of Mathematical Sciences)
  • Jeremy Hoskins
    (University of Michigan)
  • Sorin Istrail
    (Brown University)
  • Peter Jones*
    (Yale University)
  • Richard Kenyon
    (Brown University)
  • Steven Kim
    (Brown University)
  • Philip Klein
    (Brown University)
  • Andrew Knyazev
    (Mitsubishi Electric Research Laboratories)
  • Risi Kondor
    (University of Chicago)
  • Yiannis Koutis *
    (University of Puerto Rico)
  • Hyunkyoung Kwon
    (University of Alabama)
  • Roy Lederman*
    (Yale University)
  • Gilad Lerman*
    (University of Minnesota)
  • Mauro Maggioni*
    (Duke University)
  • Ahmad Mahmoody
    (Brown University)
  • Michael Mahoney *
    (University of California, Berkeley)
  • William Martin
    (Worcester Polytechnic Institute)
  • Gunnar Martinsson
    (University of Colorado)
  • David Meierfrankenfeld
    (Brown University)
  • Francois Meyer
    (University of Colorado)
  • Ankur Moitra*
    (Massachusetts Institute of Technology)
  • Nathan Monnig
    (University of Colorado Boulder)
  • Jason Morton
    (Pennsylvania State University)
  • Elchanan Mossel *
    (University of California, Berkeley)
  • Danupon Nanongkai
    (Nanyang Technological University)
  • Joe Neeman *
    (University of Texas at Austin)
  • Pedja Neskovic
    (Office of Naval Research)
  • Linda Ness
    (Applied Communication Sciences)
  • Hoi Nguyen
    (Ohio State University)
  • Sean O'Rourke*
    (Yale University)
  • Andrei Osipov*
    (Yale University)
  • Gopal Pandurangan
    (Nanyang Technological University)
  • Kavita Ramanan
    (Brown University)
  • Anup Rao
    (Yale University)
  • Ben Raphael
    (Brown University)
  • Amanda Redlich
    (Bowdoin College)
  • Igor Rivin
    (Temple University)
  • Scott Roche
    (Northeastern University)
  • Vladimir Rokhlin*
    (Yale University)
  • Mark Rudelson*
    (University of Michigan)
  • Amit Singer *
    (Princeton University)
  • Gilbert Strang
    (Massachusetts Institute of Technology)
  • Giulio Tiozzo
    (Harvard University)
  • Charalampos Tsourakakis
    (Carnegie Mellon University)
  • Eli Upfal
    (Brown University)
  • Sergey Voronin
    (University of Colorado)
  • Van Vu*
    (Yale University)
  • Ke Wang*
    (University of Minnesota)
  • Rachel Ward *
    (University of Texas at Austin)
  • Rebecca Willett *
    (University of Wisconsin)
  • James Williams
    (Yale University)
  • Grigory Yaroslavtsev
    (Pennsylvania State University)
  • Teng Zhang
    (Princeton University)
  • Xiangxiong Zhang
    (Massachusetts Institute of Technology)
MondayMay 5, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 8:55Registration11th Floor Collaborative Space
8:55 - 9:00WelcomeICERM Director11th Floor Lecture Hall
9:00 - 9:45Eigenvectors, Heat Kernels, and Low Dimensional Representation of Data SetsPeter Jones, Yale University11th Floor Lecture Hall
PDF
PDF
9:50 - 10:35Multiscale Geometric Methods for Statistical Learning and Data in High-DimensionaMauro Maggioni, Duke University11th Floor Lecture Hall
PDF
10:40 - 11:10Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Tracking Influences within Dynamic NetworksRebecca Willett, University of Wisconsin11th Floor Lecture Hall
PDF
12:00 - 2:00Lunch Break and Free Time
2:00 - 2:45Robust and Fast Subspace RecoveryGilad Lerman, University of Minnesota11th Floor Lecture Hall
PDF
2:50 - 3:35TBARoy Lederman, Yale University11th Floor Lecture Hall
3:40 - 4:10Coffee Break11th Floor Collaborative Space
4:10 - 4:55Diffuse Scattering on Graphs and Combinatorial Inverse ProblemsAnna Gilbert, University of Michigan11th Floor Lecture Hall
PDF
5:00 - 6:30Welcome Reception11th Floor Collaborative Space

TuesdayMay 6, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Covariance Matrix Estimation for the Cryo-EM Heterogeneity ProblemAmit Singer, Princeton University11th Floor Lecture Hall
PDF
9:50 - 10:35A randomized approximate nearest neighbors algorithmAndrei Osipov, Yale University11th Floor Lecture Hall
PDF
10:40 - 11:10Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Eigenvector localization, implicit regularization, and algorithmic anti-differentiation for large-scale graphs and networked dataMichael W. Mahoney, University of California, Berkeley11th Floor Lecture Hall
PDF
PDF
12:00 - 2:00Lunch Break and Free Time
2:00 - 2:45TBAVladimir Rokhlin, Yale University11th Floor Lecture Hall
2:50 - 3:35Gaps in eigenfunctions of GraphsFan Chung, University of California, San Diego11th Floor Lecture Hall
PDF
3:40 - 4:10Coffee Break11th Floor Collaborative Space
4:10 - 4:55Inverse problems on random graphs and censored block modelsEmmanuel Abbe, Princeton University11th Floor Lecture Hall

WednesdayMay 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45New Algorithms for Learning Incoherent and Overcomplete DictionariesRong Ge, Microsoft Research11th Floor Lecture Hall
PDF
PDF
9:50 - 10:35A threshold for reconstruction in stochastic block modelsJoe Neeman, University of Texas at Austin11th Floor Lecture Hall
PDF
10:40 - 11:10Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Network Clustering, the Block Stochastic Model, and a Regular GraphIoana Dumitriu, University of Washington11th Floor Lecture Hall
PDF
12:00 - 12:05Group Photo11th Floor Lecture Hall
12:05 - 2:00Lunch Break and Free Time
2:00 - 2:45Dimension reduction in the l1 norm- When and how is it possibleRachel Ward, University of Texas at Austin11th Floor Lecture Hall
PDF
2:50 - 3:35Random weighted projections, random quadratic forms and random eigenvectorsKe Wang, University of Minnesota11th Floor Lecture Hall
PDF
3:40 - 4:10Coffee Break11th Floor Collaborative Space
4:10 - 4:55Spectral algorithms for graph mining and analysisYiannis Koutis, University of Puerto Rico11th Floor Lecture Hall
PDF
7:00 - 8:30Poster Session and Dessert Reception11th Floor Collaborative Space

ThursdayMay 8, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 9:45Information-theoretic learned linear projections for dimensionality reductionLawrence Carin, Duke University11th Floor Lecture Hall
PDF
9:50 - 10:35A Polynomial Time Algorithm for Lossy Population RecoveryAnkur Moitra, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
10:40 - 11:10Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Permanent estimators via random matricesMark Rudelson, Univeristy of Michigan11th Floor Lecture Hall
PDF
PDF
12:00 - 2:00Lunch Break and Free Time
2:00 - 2:45A simple spectral algorithm for a general clustering problemVan Vu, Yale University11th Floor Lecture Hall
PDF
2:50 - 3:35Random perturbation of low rank matrices- Improving classical boundsSean O'Rourke, Yale University11th Floor Lecture Hall
PDF
3:40 - 4:10Coffee Break11th Floor Collaborative Space
4:10 - 4:55Is Belief Propagation a Spectral algorithmElchanan Mossel, University of California, Berkeley11th Floor Lecture Hall
PDF

FridayMay 9, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:50 - 10:35Panel SummaryPanel Discussion Chair: Anna Gilbert, University of Michigan11th Floor Lecture Hall
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:10 - 11:55Panel Summary11th Floor Lecture Hall
12:00 - 5:00Afternoon 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)
  • Milan Bradonjic
    (Bell Labs, Alcatel-Lucent)
  • Xavier Bresson
    (Université de Lausanne)
  • Mihai Cucuringu
    (University of California, Los Angeles)
  • Selim Esedoglu
    (University of Michigan)
  • Arjuna Flenner
    (Naval Air Warfare Center)
  • Cristina Garcia
    (Claremont Graduate University)
  • Nicolas Garcia
    (Carnegie Mellon University)
  • Steven Heilman
    (Courant Institute of Mathematical Sciences)
  • Matthias Hein
    (Universität des Saarlandes)
  • Huiyi Hu
    (University of California, Los Angeles)
  • Blake Hunter
    (University of California, Los Angeles)
  • Slav Kirov
    (Carnegie Mellon University)
  • Gitta Kutyniok
    (TU Berlin)
  • Thomas Laurent
    (Loyola Marymount University)
  • Ekaterina Merkurjev
    (University of California, Los Angeles)
  • Francois Meyer
    (University of Colorado at Boulder)
  • Braxton Osting
    (University of California, Los Angeles)
  • Mason Porter
    (University of Oxford)
  • Yuan (Alan) Qi
    (Purdue University)
  • Michaela Rombach
    (University of California, Los Angeles)
  • Dejan Slepčev
    (Carnegie Mellon University)
  • Arthur Szlam
    (City College, CUNY)
  • Xue-Cheng Tai
    (University of Bergen)
  • Yves van Gennip
    (University of Nottingham)
  • James von Brecht
    (UCLA)
  • Ulrike von Luxburg
    (Universität Hamburg)
  • Christopher White
    (University of Texas at Austin)
  • Joseph Woodworth
    (University of California, Los Angeles)
  • Dominique Zosso
    (Universtiy of California, Los Angeles)
TuesdayFebruary 4, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:15 - 9:30Welcome11th Floor Lecture Hall
9:30 - 10:30The geometry of unweighted k-nearest neighbor graphs- first results and many questionsUlrike von Luxbourg, Universitat Hamburg11th Floor Lecture Hall
10:30 - 11:30From partial differential equations to graphs- curvature and clustersYves van Gennip, University of Nottingham11th Floor Lecture Hall
PDF
PDF
11:30 - 1:00Break for Lunch
1:00 - 1:30Distance geometry on graphs via synchronizationMihai Cucuringu, UCLA11th Floor Lecture Hall
PDF
1:30 - 2:00TBAMichaela Puck Rombach, UCLA11th Floor Lecture Hall
2:00 - 2:15Break11th Floor Collaborative Space
2:15 - 3:15Applied Harmonic Analysis meets Compressed SensingGitta Kutyniok, TU Berlin11th Floor Lecture Hall
PDF
PDF
4:45 - 5:45Poster Session11th Floor Collaborative Space

WednesdayFebruary 5, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
10:00 - 11:00Scalable Gaussian process models on matrices and tensorsYuan Qi, Purdue University11th Floor Lecture Hall
PDF
11:00 - 11:30Break11th Floor Collaborative Space
11:30 - 12:00Spectral Methods for Analyzing Large DataBlake Hunter, UCLA11th Floor Lecture Hall
PDF
12:00 - 12:30Minimal Dirichlet energy partitions for graphsChris White, University of Texas at Austin11th Floor Lecture Hall
PDF
PDF

ThursdayFebruary 6, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
10:00 - 11:00Proximal splitting algorithms for two class and multiclass total variation clusteringThomas Laurent, Loyola Marymount University11th Floor Lecture Hall
PDF
PDF
11:00 - 12:00Pooling fidelity and phase recoveryArthur Szlam, City College, CUNY11th Floor Lecture Hall
PDF

FridayFebruary 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:00Random Graph Models for Image PatchesFrancois Meyer, University of Colorado at Boulder11th Floor Lecture Hall
PDF
PDF
11:00 - 11:30Break11th Floor Collaborative Space
11:30 - 12:00Non-local Beltrami and Beltrami on graphDominique Zosso, UCLA11th Floor Lecture Hall
PDF
1:30 - 2:30Graph cut, convex relaxation and continuous max-flow problemsTai Xue-Cheng, University of Bergen10th Floor Classroom
PDF

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)
  • Nathanaël François
    (Université Paris Diderot)
  • Howard Karloff
    (Yahoo! Inc.)
  • Claire Mathieu
    (École Normale Supérieure)
  • Hang Zhou
    (École Normale Supérieure)
FridayFebruary 21, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
10:00 - 11:50Research Cluster: Graphs with incomplete information

FridayFebruary 28, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
10:00 - 11:50Research Cluster: Graphs with incomplete information

FridayMarch 7, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
10:00 - 11:50Research Cluster: Graphs with incomplete information

FridayMarch 14, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
10:00 - 11:50Research Cluster: Graphs with incomplete information

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.

  • Aaron Adcock
    (Stanford University)
  • Yixin Cao
    (Hungarian Academy of Sciences (MTA))
  • Rajesh Chitnis
    (University of Maryland)
  • Erik Demaine
    (Massachusetts Institute of Technology)
  • Hossein Esfandiari
    (University of Maryland)
  • Fedor Fomin
    (University of Bergen)
  • Kyle Fox
    (University of Illinois at Urbana-Champaign)
  • MohammadTaghi Hajiaghayi
    (University of Maryland)
  • Philip Klein
    (Brown University)
  • Michael Langston
    (University of Tennessee)
  • Vahid Liaghat
    (University of Maryland)
  • Daniel Lokshtanov
    (University of Bergen)
  • Daniel Marx
    (Hungarian Academy of Sciences (MTA))
  • Morteza Monemizadeh
    (University of Maryland)
  • Shay Mozes
    (Interdisciplinary Center for Neural Computation at Hebrew University)
  • Michael O'Brien
    (North Carolina State University)
  • Felix Reidl
    (RWTH Aachen)
  • Fernando Sanchez Villaamil
    (RWTH Aachen)
  • Saket Saurabh
    (Institute of Mathematical Sciences)
  • Aaron Schild
    (Princeton University)
  • Aikaterini Sotiraki
    (Massachusetts Institute of Technology)
  • Blair Sullivan
    (North Carolina State University)
  • Ali Vakilian
    (Massachusetts Institute of Technology)
ThursdayApril 24, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
8:30 - 9:00Registration11th Floor Collaborative Space
9:00 - 10:20Basic techniques of fixed-parameter tractability (Part 1)Saket Saurabh, Institute of Mathematical Sciences11th Floor Lecture Hall
PDF
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:00 - 12:30Basic techniques of fixed-parameter tractability (Part 2)Daniel Lokshtanov, University of Bergen11th Floor Lecture Hall
PDF
12:30 - 2:00Break for Lunch
2:00 - 3:30KernelizationSaket Saurabh, Institute of Mathematical Sciences11th Floor Lecture Hall
PDF
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research

FridayApril 25, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:20Treewidth and applicationsFedor Fomin, University of Bergen11th Floor Lecture Hall
PDF
10:30 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 11:15Open Problem Session11th Floor Lecture Hall
11:15 - 12:45Minors and AlgorithmsErik Demaine, Massachusetts Institute of Technology11th Floor Lecture Hall
PDF
12:45 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research

SaturdayApril 26, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:20Approximation AlgorithmsMohammad Taghi Hajiaghayi, University of Maryland11th Floor Lecture Hall
PDF
10:30 - 11:00Coffee/Tea Break11th Floor Collaborative Space
11:00 - 12:30Lower boundsDaniel Marx, Hungarian Academy of Sciences (MTA)11th Floor Lecture Hall
PDF
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research

SundayApril 27, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:20SeparatorsDaniel Marx, Hungarian Academy of Sciences (MTA)11th Floor Lecture Hall
PDF
10:30 - 11:00Coffee/Tea Break
11:00 - 12:30Connecting to the Real-World ApplicationsBlair Sullivan, North Carolina State University11th Floor Lecture Hall
PDF
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break
4:00 - 5:00Research

MondayApril 28, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Opening Session11th Floor Lecture Hall
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Lecture Hall
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research
5:00 - 5:30Problem Session Update11th Floor Lecture Hall

TuesdayApril 29, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Research
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Lecture Hall
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research
5:00 - 5:30Problem Session Update11th Floor Lecture Hall

WednesdayApril 30, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Research
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Lecture Hall
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research
5:00 - 5:30Problem Session Update10th floor classroom

ThursdayMay 1, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Research
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Lecture Hall
12:30 - 2:00Break for Lunch
2:00 - 3:30Research
3:30 - 4:00Coffee/Tea Break11th Floor Collaborative Space
4:00 - 5:00Research
5:00 - 5:30Problem Session Update11th Floor Lecture Hall

FridayMay 2, 2014
TimeDescriptionSpeakerLocationAbstractsSlides
9:00 - 10:15Research
10:15 - 10:45Coffee/Tea Break11th Floor Collaborative Space
10:45 - 12:00Research
12:00 - 12:30Problem Session Update11th Floor Collaborative Space
12:30 - 2:30Break for Lunch
2:30 - 5:00Closing Session/Wrap-Up11th Floor Lecture Hall