2026-07-21T23:51:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23380 2025-10-02T12:53:32Z ddc:004 open_access

Near-Optimal Trace Reconstruction for Mildly Separated Strings Aamand, Anders Liu, Allen Narayanan, Shyam Trace Reconstruction deletion channel sample complexity In the trace reconstruction problem our goal is to learn an unknown string x ∈ {0,1}ⁿ given independent traces of x. A trace is obtained by independently deleting each bit of x with some probability δ and concatenating the remaining bits. It is a major open question whether the trace reconstruction problem can be solved with a polynomial number of traces when the deletion probability δ is constant. The best known upper bound and lower bounds are respectively exp(Õ(n^{1/5})) [Zachary Chase, 2021a] and ̃ Ω(n^{3/2}) [Zachary Chase, 2021b]. Our main result is that if the string x is mildly separated, meaning that the number of zeros between any two ones in x is at least polylog n, and if δ is a sufficiently small constant, then the trace reconstruction problem can be solved with O(n log n) traces and in polynomial time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anders Aamand and Allen Liu and Shyam Narayanan 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.3 urn:nbn:de:0030-drops-233801 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.3 eng https://creativecommons.org/licenses/by/4.0/legalcode