Coded trace reconstruction in a constant number of traces

Abstract

The coded trace reconstruction problem asks to construct a code $C\subset \{0,1{\}}^n$ such that any $x\in C$ is recoverable from independent outputs ("traces") of $x$ from a binary deletion channel (BDC). We present binary codes of rate $1-\epsilon$ that are efficiently recoverable from $\exp (O_q({\log }^{1/3}(\frac{1}{\epsilon })))$ (a constant independent of $n$) traces of a ${\mathrm{BDC}}_q$ for any constant deletion probability $q\in (0,1)$. We also show that, for rate $1-\epsilon$ binary codes, $\tilde{\hat{I}}\text{c◯}({\log }^{5/2}(1/\epsilon ))$ traces are required. The results follow from a pair of black-box reductions that show that average-case trace reconstruction is essentially equivalent to coded trace reconstruction. We also show that there exist codes of rate $1-\epsilon$ over an $O_{\epsilon }(1)$-sized alphabet that are recoverable from $O(\log (1/\epsilon ))$ traces, and that this is tight.

34 pages, 2 figures; FOCS 2020