PACM Colloquium: Trace reconstruction for the deletion channel

Yuval Peres - Microsoft Research
Oct 2 2017 - 4:00pm
Event type: 
PACM Colloquium
214 Fine Hall

In the trace reconstruction problem, an unknown string $x$ of $n$ bits is observed through the deletion channel, which deletes each bit with some constant 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 linear in $n$.  Until recently, the best upper bound was exponential in the square root of $n$. We improve the square root to a cube root using statistics of individual output bits and some complex analysis;  this bound is sharp for reconstruction algorithms that only use this statistical information. (Similar results were obtained independently and concurrently by De, O’Donnell and Servedio).  If the string $x$  is random and $q<1/2$, we can show a subpolynomial number of traces suffices by comparison to a biased random walk.   (Joint works with Fedor Nazarov, STOC 2017 and with Alex Zhai, FOCS 2017). In very recent work with Nina Holden and Robin Pemantle, we removed the restriction $q<1/2$ for random inputs.

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 280 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 Mathematicians, and a plenary lecturer at the Mathematics Congress of the Americas in 2017. He has advised 21 Ph.D. students. In 2016 he was elected as a foreign associate to the U.S. National Academy of Sciences.