Chen, Xi
[Verfasser:in];
De, Anindya
[Verfasser:in];
Lee, Chin Ho
[Verfasser:in];
Servedio, Rocco A.
[Verfasser:in];
Sinha, Sandip
[Verfasser:in]
;
Xi Chen and Anindya De and Chin Ho Lee and Rocco A. Servedio and Sandip Sinha
[Mitwirkende:r]
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime
Titel:
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime
Beteiligte:
Chen, Xi
[Verfasser:in];
De, Anindya
[Verfasser:in];
Lee, Chin Ho
[Verfasser:in];
Servedio, Rocco A.
[Verfasser:in];
Sinha, Sandip
[Verfasser:in]
Erschienen:
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
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.