  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-\varepsilon$ that are efficiently recoverable from
${\exp(O_q(\log^{1/3}(\frac{1}{\varepsilon})))}$ (a constant independent of
$n$) traces of a $\operatorname{BDC}_q$ for any constant deletion probability
$q\in(0,1)$. We also show that, for rate $1-\varepsilon$ binary codes, $\tilde
\Omega(\log^{5/2}(1/\varepsilon))$ 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-\varepsilon$ over an $O_{\varepsilon}(1)$-sized
alphabet that are recoverable from $O(\log(1/\varepsilon))$ traces, and that
this is tight.
