@article{5dd7f61b69b24d95b74606506d04d59a,

title = "Lower bounds for trace reconstruction",

abstract = "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.",

keywords = "Deletion channel, Sample complexity, Strings",

author = "Nina Holden and Russell Lyons",

note = "Funding Information: Acknowledgments. We thank the anonymous referees for useful comments and careful reading of our paper. Most of this paper was written while visiting Microsoft Research Redmond, and we thank Microsoft for the hospitality. The first author was supported in part by an internship at Microsoft Research and by a fellowship from the Norwegian Research Council. The second author was supported in part by NSF Grant DMS-1612363. Funding Information: We thank the anonymous referees for useful comments and careful reading of our paper. Most of this paper was written while visiting Microsoft Research Redmond, and we thank Microsoft for the hospitality. The first author was supported in part by an internship at Microsoft Research and by a fellowship from the Norwegian Research Council. The second author was supported in part by NSF Grant DMS-1612363. Publisher Copyright: {\textcopyright} 2020 Institute of Mathematical Statistics.",

year = "2020",

month = apr,

doi = "10.1214/19-AAP1506",

language = "English (US)",

volume = "30",

pages = "503--525",

journal = "Annals of Applied Probability",

issn = "1050-5164",

publisher = "Institute of Mathematical Statistics",

number = "2",

}