Trace reconstruction for the deletion channel

יום ב', 15/10/2018 - 14:00

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 of order $n^{1.25}$. Until 2016, the best upper bound available
was exponential in the square root of $n$. With Fedor Nazarov, we improve the square root to
a cube root using complex analysis (bounds for Littlewood polynomials on the unit circle).
This upper 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 work with Alex Zhai, FOCS 2017). With Nina Holden and
Robin Pemantle (COLT 2018), we removed the restriction $q<1/2$ for random inputs.