Yuval Peres: Trace reconstruction for the deletion channel
Yuval Peres, Microsoft Research, Redmond
Date: Tuesday, May 02, 2017
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Refreshments: 3:45 PM
Location: Kiva G449
Host: Ankur Moitra
Contact: Deborah Goodwin, 617.324.7303, email@example.com
Speaker URL: None
TALK: Yuval Peres: Trace reconstruction for the deletion channel
Abstract: 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 2016, the best upper bound (due to Holenstein, Mitzenmacher, Panigrahy and Wieder 2008) 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. (Joint work with Fedor Nazarov, STOC 2017; similar results were obtained independently and concurrently by De, ODonnell and Servedio). In very recent work with Alex Zhai, we showed that If the string $x$ is random and $q<1/2$, then a subpolynomial number of traces suffices.
Created by Deborah Goodwin at Thursday, April 27, 2017 at 9:02 AM.