Trace reconstruction for the deletion channel

Trace reconstruction for the deletion channel

-
Yuval Peres , Microsoft Research
Fine Hall 214

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