Lower bounds for trace reconstruction

2018/08/04 by Holden, Nina, Lyons, Russell · 2 citations
#60K30 #62C20 #68Q25 #68Q87 #68W32 68W40 #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR) #Statistics Theory (math.ST)

paper · doi:10.48550/arxiv.1808.02336

Abstract

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

Cited by

• New Bounds for Circular Trace Reconstruction
• Trace Reconstruction with Language Models

Related

• Near-Optimal Trace Reconstruction for Mildly Separated Strings
• Trace reconstruction with exp( O( n^1/3 ) ) samples
• Approximate Trace Reconstruction from a Single Trace
• New Bounds for Circular Trace Reconstruction
• Trace reconstruction with varying deletion probabilities