Substring Density Estimation From Traces

In the trace reconstruction problem, one seeks to reconstruct a binary string s from a collection of traces, each of which is obtained by passing s through a deletion channel. It is known that <tex-math notation="LaTeX">exp (Õ(n1/5)) </tex-math> traces suffice to reconstruct any length-n string with high probability. We consider a variant of the trace reconstruction problem where the goal is to recover a "density map" that indicates the locations of each length-k substring throughout s. We show that when <tex-math notation="LaTeX">k = c log n </tex-math> where c is constant, <tex-math notation="LaTeX">ε ⁻²· poly (n) </tex-math> traces suffice to recover the density map with error at most <tex-math notation="LaTeX">ε </tex-math> . As a result, when restricted to a set of source strings whose minimum "density map distance" is at least <tex-math notation="LaTeX">1/poly(n) </tex-math> , the trace reconstruction problem can be solved with polynomially many traces.