BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium: Two problems: Planar bipartite matching and reconst
 ruction for the deletion channel
DTSTART:20181005T103000
DTEND:20181005T113000
DTSTAMP:20260406T210335Z
UID:e99aac52042316fbe81054c4c99efbbac8e92011292d936f3d206f58
CATEGORIES:Conferences - Seminars
DESCRIPTION:By: Yuval Peres - Microsoft Research\nVideo of his talk\n\nAbs
 tract:\nIn the first part of the talk\, I will discuss bipartite matching 
 for random points in two dimensions: The optimal  matching was analyzed b
 y Ajtai\, Komlos\, Tusnady (1984)\; it is an open problem to analyze greed
 y matchings. With N. Holden and A. Zhai we showed that gravitational matc
 hing is almost optimal. (See  http://www.ams.org/publications/journals/n
 otices/201705/rnoti-cvr1.pdf  or the PNAS article http://www.pnas.org/c
 ontent/early/2018/09/06/1720804115 ).  \nIn the second (unrelated) part\
 , I will survey the trace reconstruction problem (arising in DNA storage):
   An unknown string x of n bits is observed through  the deletion channe
 l\, which deletes each bit with probability q\, yielding a contracted stri
 ng.  How many independent outputs (traces) of the deletion channel are ne
 eded to reconstruct x with high probability? The best lower bound known is
  essentially linear in n.  Until 2016\, the best upper bound was exponent
 ial in the square root of n. With Fedor Nazarov we improved the square roo
 t to a cube root (STOC 2017\;  also obtained by De\, O’Donnell and Serv
 edio). However\, If the string $x$  is random\, then a sub-polynomial num
 ber of traces suffices (Joint work with Alex Zhai\, FOCS 2017\, for q<1/2\
 ; and with Nina Holden and Robin Pemantle \, COLT 2018\, for general q).\n
 \nBio:\nYuval Peres is a Principal Researcher at Microsoft Research in Red
 mond. He obtained his Ph.D. at the Hebrew University\, Jerusalem in 1990\,
  and later taught there and at the University of California\, Berkeley. He
  has published more than 300 research papers and has co-authored books on 
 Brownian motion\, Markov chains\, Probability on Networks\, Fractals\, and
  Game Theory. Yuval was awarded the Rollo Davidson Prize in 1995\, the Lo
 ève Prize in 2001\, and the David P. Robbins Prize in 2011. He was an inv
 ited speaker at the 2002 International Congress of Math. and in the 2008 E
 uropean Congress\, and was a  plenary lecturer at the Math. Congress of t
 he Americas in 2017. He has advised 22 Ph.D. students. He is a fellow of t
 he American Math. Society and the Institute of Mathematical Statistics. In
  2016 he was elected to the U.S. National Academy of Sciences.\n\nMore inf
 ormation\n\n 
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR