BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Approximate Matchings in Graph Streams and in the Simultaneous Com
 munication Model
DTSTART:20170615T093000
DTEND:20170615T101500
DTSTAMP:20260929T023825Z
UID:39924957863871bf20c9897bd61e297e8c796be2be924de21d400ee7
CATEGORIES:Conferences - Seminars
DESCRIPTION:Sanjeev Khanna\, University of Pennsylvania\nThe maximum match
 ing problem is among the most well-studied problems in combinatorial optim
 ization with many applications. We consider the problem of approximating a
  maximum matching in graph streams where the input graph is revealed as a 
 stream of edge updates that may include both edge insertions and deletions
 . The goal is to design a streaming algorithm that computes an approximate
  matching in sublinear space\, that is\, using space that is substantially
  smaller than the space needed to store all the edges in the graph.\nIn th
 is talk\, we will describe some progress on this problem that precisely ch
 aracterizes the tradeoff between the space available to the algorithm and 
 the quality of the matching approximation. As it turns out\, the study of 
 sublinear space algorithms for matchings is intimately connected to unders
 tanding communication complexity of solving the matching problem in a dist
 ributed model of computation\, called the simultaneous communication model
 . We will also present some very recent developments on the matching probl
 em in the simultaneous model which show that a simple assumption on how th
 e graph is partitioned completely alters the tractability of the problem.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR