The ACO Seminar (2019–2020)

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}(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.

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.