EE Systems Seminar

In the trace reconstruction problem, an unknown string x of n bits is observed through the deletion channel, which deletes each bit of x with probability 1/2, yielding a contracted string (where the original location of each bit in the output is unknown). How many independent copies of this output are needed to reconstruct x with high probability? It is an open question whether poly(n) samples suffice. Prior to this work, the best upper bound, due to Holenstein, Mitzenmacher, Panigrahy, and Wieder (2008), was exponential in the square root of n. We improve this bound to exponential in the cube root of n, using statistics of individual bits in the output, and show that this bound is sharp in the restricted model where this is the only information used. Our method, which uses classical complex analysis, can also handle insertions and larger alphabets. (Joint work with Fedja Nazarov.)

Yuval Peres is a Principal Researcher at Microsoft Research. Previously, he was a Professor at the University of California, Berkeley and at the Hebrew University, Jerusalem.  He has published more than 250 research papers with 170 collaborators (and two of his favorite collaborators are at Caltech). Yuval has co-authored books on Brownian motion, Markov chains, Probability on Networks, Fractals, and Game Theory. He was awarded the Rollo Davidson Prize in 1995, the Loeve Prize in 2001, and the David P. Robbins Prize in 2011. He was an invited speaker at the 2002 International Congress of Mathematicians and at the 2008 European Congress. In 2016 he was elected to the National Academy of Sciences.