Lower bounds for trace reconstruction

Nina Holden, Russell Lyons

Research output: Contribution to journalArticlepeer-review


In the trace reconstruction problem, an unknown bit string x ∈ {0, 1}n is sent through a deletion channel where each bit is deleted independently with some probability q ∈ (0, 1), yielding a contracted string x. How many i.i.d. samples of xare needed to reconstruct x with high probability? We prove that there exist x, y ∈ {0, 1}n such that at least cn5/4/ √log n traces are required to distinguish between x and y for some absolute constant c, improving the previous lower bound of cn. Furthermore, our result improves the previously known lower bound for reconstruction of random strings from c log2 n to c log9/4 n/√log log n.

Original languageEnglish (US)
Pages (from-to)503-525
Number of pages23
JournalAnnals of Applied Probability
Issue number2
StatePublished - Apr 2020


  • Deletion channel
  • Sample complexity
  • Strings

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Lower bounds for trace reconstruction'. Together they form a unique fingerprint.

Cite this