Processing math: 100%

ACO The ACO Seminar (2019–2020)

September 5, 3:30pm, Wean 8220
Joshua Brakensiek, Stanford University
Coded trace reconstruction in a constant number of traces

Abstract:

The coded trace reconstruction problem asks to construct a code C{0,1}n such that any xC 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.


Back to the ACO home page Back to the ACO Seminar schedule