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 exp (∼ O(n^1/5)) 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 k = cn where c is constant, ϵ ^-2ċ poly (n) traces suffice to recover the density map with error at most ϵ . As a result, when restricted to a set of source strings whose minimum 'density map distance' is at least 1/ poly(n) , the trace reconstruction problem can be solved with polynomially many traces.