Coded trace reconstruction in a constant number of traces

The coded trace reconstruction problem asks to construct a code C ⊂ 0,1nsuch that any x ∈ C is recoverable from independent outputs (“traces”) of x from a binary deletion channel (BDC). We present binary codes of rate 1-ε that are efficiently recoverable from exp(Oq(log1/3([1/(ε)]))) (a constant independent of n) traces of a BDCq for any constant deletion probability q ∈ (0,1). We also show that, for rate 1 -ε binary codes, Ω(log5/2(1/ε)) 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 -ε over an Oε(1)-sized alphabet that are recoverable from O(log(1/ε)) traces, and that this is tight.