License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2021.20
URN: urn:nbn:de:0030-drops-135595
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13559/
Chen, Xi ;
De, Anindya ;
Lee, Chin Ho ;
Servedio, Rocco A. ;
Sinha, Sandip
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime
Abstract
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.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs.ITCS.2021.20,
author = {Xi Chen and Anindya De and Chin Ho Lee and Rocco A. Servedio and Sandip Sinha},
title = {{Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime}},
booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
pages = {20:1--20:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-177-1},
ISSN = {1868-8969},
year = {2021},
volume = {185},
editor = {James R. Lee},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13559},
URN = {urn:nbn:de:0030-drops-135595},
doi = {10.4230/LIPIcs.ITCS.2021.20},
annote = {Keywords: trace reconstruction}
}
|
Keywords: |
|
trace reconstruction |
|
Collection: |
|
12th Innovations in Theoretical Computer Science Conference (ITCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
04.02.2021 |
