BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Sublinear Algorithms for Modern Graph Analysis
DTSTART:20150223T101500
DTEND:20150223T113000
DTSTAMP:20260407T183824Z
UID:1933c43e76d88da3078abef4ffa1a4139d5fb6b1942bbc4741255551
CATEGORIES:Conferences - Seminars
DESCRIPTION:By : Michael Kapralov - IBM T. J. Watson Research Center\nIC F
 aculty candidateAbstract :\nGraphs are a common abstraction for representi
 ng large social and information networks\, and a powerful set of algorithm
 ic primitives has been developed for their analysis. As the sizes of moder
 n datasets grow\, however\, many classical polynomial time (and sometimes 
 even linear time) solutions become prohibitively expensive. This calls for
  sublinear algorithms\, i.e. algorithms whose resource requirements are su
 bstantially smaller than the size of the input that they operate on.\nIn t
 his talk\, we describe a new approach to the problem of approximating the 
 size of maximum matching in a large graph given as a stream of edge update
 s using sublinear space. The matching problem is one of the most well-stud
 ied questions in combinatorial optimization\, and has important applicatio
 ns in modern big data analysis (e.g. online advertising). We obtain a poly
 logarithmic approximation to maximum matching size using space sublinear i
 n the number of *vertices* in the graph and exponentially smaller than pre
 viously known. This is the first algorithm for a graph problem that achiev
 es truly sublinear space in the streaming setting\, suggesting the possibi
 lity of a new class of more efficient graph analysis primitives.Bio :\nMic
 hael Kapralov is a Herman Goldstine Postdoctoral Fellow at the IBM T.J. Wa
 tson Research Center. Michael obtained his Ph.D. from Stanford University 
 in 2012\, after which he spent two years as a postdoc in the Theory of Com
 putation Group at MIT CSAIL. His research interests are in design of effic
 ient algorithms. He has worked on various questions in theoretical foundat
 ions of big data analysis: algorithms for solving graph problems on massiv
 e inputs that achieve sublinear runtime\, can operate under tight restrict
 ions on space (streaming algorithms) and communication (sketching algorith
 ms) or can deal with uncertainty in future inputs (online algorithms). His
  most recent interests include sparse recovery and Fourier sampling.More i
 nformation
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR