A Caltech Library Service

Trace Reconstruction with Bounded Edit Distance

Sima, Jin and Bruck, Jehoshua (2021) Trace Reconstruction with Bounded Edit Distance. In: 2021 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 2519-2524. ISBN 978-1-5386-8209-8.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The trace reconstruction problem studies the number of noisy samples needed to recover an unknown string x ∈ {0,1}^n with high probability, where the samples are independently obtained by passing x through a random deletion channel with deletion probability q. The problem is receiving significant attention recently due to its applications in DNA sequencing and DNA storage. Yet, there is still an exponential gap between upper and lower bounds for the trace reconstruction problem. In this paper we study the trace reconstruction problem when x is confined to an edit distance ball of radius k, which is essentially equivalent to distinguishing two strings with edit distance at most k. It is shown that n^(O(k)) samples suffice to achieve this task with high probability.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper ItemTechnical Report
Sima, Jin0000-0003-4588-9790
Bruck, Jehoshua0000-0001-8474-0812
Additional Information:© 2021 IEEE. This work was supported in part by NSF grant CCF-1816965 and NSF grant CCF-1717884.
Funding AgencyGrant Number
Record Number:CaltechAUTHORS:20211110-153719711
Persistent URL:
Official Citation:J. Sima and J. Bruck, "Trace Reconstruction with Bounded Edit Distance," 2021 IEEE International Symposium on Information Theory (ISIT), 2021, pp. 2519-2524, doi: 10.1109/ISIT45174.2021.9518244
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:111816
Deposited By: Tony Diaz
Deposited On:11 Nov 2021 19:21
Last Modified:11 Nov 2021 19:21

Repository Staff Only: item control page