2020/08/27 by Xi Chen, Chen, Xi, Anindya De +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #68Q87 (Primary) 68Q25 (Secondary) #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #F.2.0 #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2008.12386
openalex publication_date 2020/08/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the trace reconstruction problem, an unknown source string x ∈ \0,1\n is sent through a probabilistic deletion channel which independently deletes each bit with probability δ and concatenates the surviving bits, yielding a trace of x. The problem is to reconstruct x given independent traces. This problem has received much attention in recent years both in the worst-case setting where x may be an arbitrary string in \0,1\n \citeDOS17,NazarovPeres17,HHP18,HL18,Chase19 and in the average-case setting where x is drawn uniformly at random from \0,1\n \citePeresZhai17,HPP18,HL18,Chase19. This paper studies trace reconstruction in the smoothed analysis setting, in which a ``worst-case'' string x\worst is chosen arbitrarily from \0,1\n, and then a perturbed version \bx of x\worst is formed by independently replacing each coordinate by a uniform random bit with probability σ. The problem is to reconstruct \bx given independent traces from it. Our main result is an algorithm which, for any constant perturbation rate 0