2026-08-16T20:23:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13559 2024-03-06T10:52:18Z ddc:004 open_access

Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime Chen, Xi De, Anindya Lee, Chin Ho Servedio, Rocco A. Sinha, Sandip trace reconstruction In the trace reconstruction problem, an unknown source string x ∈ {0,1}ⁿ is transmitted through a probabilistic deletion channel which independently deletes each bit with some fixed probability δ and concatenates the surviving bits, resulting in a trace of x. The problem is to reconstruct x given access to independent traces. Trace reconstruction of arbitrary (worst-case) strings is a challenging problem, with the current state of the art for poly(n)-time algorithms being the 2004 algorithm of Batu et al. [T. Batu et al., 2004]. This algorithm can reconstruct an arbitrary source string x ∈ {0,1}ⁿ in poly(n) time provided that the deletion rate δ satisfies δ ≤ n^{-(1/2 + ε)} for some ε > 0. In this work we improve on the result of [T. Batu et al., 2004] by giving a poly(n)-time algorithm for trace reconstruction for any deletion rate δ ≤ n^{-(1/3 + ε)}. Our algorithm works by alternating an alignment-based procedure, which we show effectively reconstructs portions of the source string that are not "highly repetitive", with a novel procedure that efficiently determines the length of highly repetitive subwords of the source string. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Xi Chen and Anindya De and Chin Ho Lee and Rocco A. Servedio and Sandip Sinha 2021 Is Part Of LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2021.20 urn:nbn:de:0030-drops-135595 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.20 eng https://creativecommons.org/licenses/by/3.0/legalcode