← All problems

10 Lectures and 42 Open Problems — The Deletion Channel

For a binary string x∈{0,1}mx\in\{0,1\}^m, a trace is formed by independently deleting each bit with probability qq and concatenating the bits that remain. The first question sets q=1/2q=1/2 and asks, verbatim, “What are the asymptotics of D(n;12)\mathcal{D}\left(n;\frac12\right)?” The notation D(n;1/2)\mathcal D(n;1/2) is not defined in the question, so its object and intended asymptotic regime cannot be specified more precisely without changing the question. Holden and Lyons (2020)

The second question asks, verbatim: “What are the two (distinct) binary sequences x(1)x^{(1)} and x(2)x^{(2)} that are more difficult to distinguish (let’s say that the receiver knows that either x(1)x^{(1)} or x(2)x^{(2)} was sent but not which)?” In the deletion-channel setting, distinguishing a fixed pair means using independent traces to decide which input was sent; the question does not specify the sequences’ lengths or a target error probability. Holden and Lyons (2020)

Background

Trace reconstruction asks how many independent traces suffice to recover an unknown string. Pairwise distinction is a related problem: it asks how many traces are needed when the receiver knows the input is one of two specified strings. The problem was introduced as an abstraction of a bioinformatics task of reconstructing a common ancestor from genetic sequences. Upper bounds based on single-bit statistics improved from exponential scale exp⁡(n1/2polylog⁡n)\exp(n^{1/2}\operatorname{polylog}n) to exp⁡(O(n1/3))\exp(O(n^{1/3})) traces. Holden and Lyons (2020)

A useful measure of how hard a pair is to distinguish is the total variation distance between its one-trace output distributions: small distance means that one trace carries little information for deciding between the inputs. For the alternating-pattern pair below, Holden and Lyons bound this distance on the scale of n−3/4n^{-3/4}, up to a logarithmic factor. Their coupling argument makes the traces agree with high probability by matching the retained pattern blocks on either side of the pair’s single defect. Holden and Lyons (2020)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.