Trace reconstruction with exp(O(n 1/3 )) samples

In the trace reconstruction problem, an unknown bit string x ∈ {0,1} n is observed through the deletion channel, which deletes each bit of x with some constant probability q , yielding a contracted string x . How many independent copies of x are needed to reconstruct x with high probability? Prior to this work, the best upper bound, due to Holenstein, Mitzenmacher, Panigrahy, and Wieder (2008), was exp( O ( n 1/2 )). We improve this bound to exp( O ( n 1/3 )) using statistics of individual bits in the output and show that this bound is sharp in the restricted model where this is the only information used. Our method, that uses elementary complex analysis, can also handle insertions. Similar results were obtained independently and simultaneously by Anindya De, Ryan O'Donnell and Rocco Servedio.

Authors

• Fedor Nazarov
• Yuval Peres

Keywords

• Deletion channel
• Generating function
• Littlewood polynomial
• Reconstruction
• Sample complexity