LOWER BOUNDS FOR TRACE RECONSTRUCTION

• 成果类型: Article
• 署名作者: Holden, Nina; Lyons, Russell
• 署名单位: Massachusetts Institute of Technology (MIT); Indiana University System; Indiana University Bloomington
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/19-AAP1506
• 发表日期: 2020
• 页码: 503-525
• 关键词: random-walk; scenery

摘要

In the trace reconstruction problem, an unknown bit string x is an element of {0, 1}(n) is sent through a deletion channel where each bit is deleted independently with some probability q is an element of (0, 1), yielding a contracted string (x) over tilde. How many i.i.d. samples of (x) over tilde are needed to reconstruct x with high probability? We prove that there exist x, y is an element of {0, 1}(n) such that at least cn(5/4)/root 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 log(2) n to c log(9/4) n/root log log n.