The coded trace reconstruction problem asks to construct a code
C⊂{0,1}n such 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.
Joint work with Ray Li and Bruce Spang.
Full text available
here.
Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.