Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

Nina Holden, Robin Pemantle, Yuval Peres

Research output: Contribution to journalConference articlepeer-review


The deletion-insertion channel takes as input a bit string x ∈ {0, 1}n, and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover x from many independent outputs (called “traces”) of the deletion-insertion channel applied to x. We show that if x is chosen uniformly at random, then exp(O(log1/3 n)) traces suffice to reconstruct x with high probability. For the deletion channel with deletion probability q < 1/2 the earlier upper bound was exp(O(log1/2 n)). The case of q ≥ 1/2 or the case where insertions are allowed has not been previously analysed, and therefore the earlier upper bound was as for worst-case strings, i.e., exp(O(n1/3)). A key ingredient in our proof is a delicate two-step alignment procedure where we estimate the location in each trace corresponding to a given bit of x. The alignment is done by viewing the strings as random walks, and comparing the increments in the walk associated with the input string and the trace, respectively.

Original languageEnglish (US)
Pages (from-to)1799-1840
Number of pages42
JournalProceedings of Machine Learning Research
StatePublished - 2018
Event31st Annual Conference on Learning Theory, COLT 2018 - Stockholm, Sweden
Duration: Jul 6 2018Jul 9 2018


  • Deletion channel
  • Sample complexity
  • Trace reconstruction

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability


Dive into the research topics of 'Subpolynomial trace reconstruction for random strings and arbitrary deletion probability'. Together they form a unique fingerprint.

Cite this