IC Colloquium: Two problems: Planar bipartite matching and reconstruction for the deletion channel
Event details
| Date | 05.10.2018 |
| Hour | 10:30 › 11:30 |
| Location | |
| Category | Conferences - Seminars |
By: Yuval Peres - Microsoft Research
Video of his talk
Abstract:
In the first part of the talk, I will discuss bipartite matching for random points in two dimensions: The optimal matching was analyzed by Ajtai, Komlos, Tusnady (1984); it is an open problem to analyze greedy matchings. With N. Holden and A. Zhai we showed that gravitational matching is almost optimal. (See http://www.ams.org/publications/journals/notices/201705/rnoti-cvr1.pdf or the PNAS article http://www.pnas.org/content/early/2018/09/06/1720804115 ).
In 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 channel, which deletes each bit with probability q, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct x with high probability? The best lower bound known is essentially linear in n. Until 2016, the best upper bound was exponential in the square root of n. With Fedor Nazarov we improved the square root to a cube root (STOC 2017; also obtained by De, O’Donnell and Servedio). However, If the string $x$ is random, then a sub-polynomial number 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).
Bio:
Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. 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 invited speaker at the 2002 International Congress of Math. and in the 2008 European Congress, and was a plenary lecturer at the Math. Congress of the Americas in 2017. He has advised 22 Ph.D. students. He is a fellow of the American Math. Society and the Institute of Mathematical Statistics. In 2016 he was elected to the U.S. National Academy of Sciences.
More information
Video of his talk
Abstract:
In the first part of the talk, I will discuss bipartite matching for random points in two dimensions: The optimal matching was analyzed by Ajtai, Komlos, Tusnady (1984); it is an open problem to analyze greedy matchings. With N. Holden and A. Zhai we showed that gravitational matching is almost optimal. (See http://www.ams.org/publications/journals/notices/201705/rnoti-cvr1.pdf or the PNAS article http://www.pnas.org/content/early/2018/09/06/1720804115 ).
In 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 channel, which deletes each bit with probability q, yielding a contracted string. How many independent outputs (traces) of the deletion channel are needed to reconstruct x with high probability? The best lower bound known is essentially linear in n. Until 2016, the best upper bound was exponential in the square root of n. With Fedor Nazarov we improved the square root to a cube root (STOC 2017; also obtained by De, O’Donnell and Servedio). However, If the string $x$ is random, then a sub-polynomial number 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).
Bio:
Yuval Peres is a Principal Researcher at Microsoft Research in Redmond. 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 invited speaker at the 2002 International Congress of Math. and in the 2008 European Congress, and was a plenary lecturer at the Math. Congress of the Americas in 2017. He has advised 22 Ph.D. students. He is a fellow of the American Math. Society and the Institute of Mathematical Statistics. In 2016 he was elected to the U.S. National Academy of Sciences.
More information
Practical information
- General public
- Free
- This event is internal
Contact
- Host: Michael Kapralov