2026-07-20T11:57:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15522 2024-03-06T10:55:30Z ddc:004 open_access

Approximate Trace Reconstruction via Median String (In Average-Case) Chakraborty, Diptarka Das, Debarati Krauthgamer, Robert Trace Reconstruction Approximation Algorithms Edit Distance String Median We consider an approximate version of the trace reconstruction problem, where the goal is to recover an unknown string s ∈ {0,1}ⁿ from m traces (each trace is generated independently by passing s through a probabilistic insertion-deletion channel with rate p). We present a deterministic near-linear time algorithm for the average-case model, where s is random, that uses only three traces. It runs in near-linear time Õ(n) and with high probability reports a string within edit distance Õ(p² n) from s, which significantly improves over the straightforward bound of O(pn). Technically, our algorithm computes a (1+ε)-approximate median of the three input traces. To prove its correctness, our probabilistic analysis shows that an approximate median is indeed close to the unknown s. To achieve a near-linear time bound, we have to bypass the well-known dynamic programming algorithm that computes an optimal median in time O(n³). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diptarka Chakraborty and Debarati Das and Robert Krauthgamer 2021 Is Part Of LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2021.11 urn:nbn:de:0030-drops-155228 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.11 eng https://creativecommons.org/licenses/by/4.0/legalcode