Sima, Jin and Bruck, Jehoshua (2021) Trace Reconstruction with Bounded Edit Distance. Parallel and Distributed Systems Group Technical Reports, etr152. California Institute of Technology , Pasadena, CA. (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20210624-215307865
![]() |
PDF
- Submitted Version
See Usage Policy. 320kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210624-215307865
Abstract
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 p. 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: | Report or Paper (Technical Report) | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
ORCID: |
| |||||||||
Group: | Parallel and Distributed Systems Group | |||||||||
Series Name: | Parallel and Distributed Systems Group Technical Reports | |||||||||
Issue or Number: | etr152 | |||||||||
Record Number: | CaltechAUTHORS:20210624-215307865 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20210624-215307865 | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 109575 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | George Porter | |||||||||
Deposited On: | 25 Jun 2021 14:55 | |||||||||
Last Modified: | 10 Nov 2021 15:38 |
Repository Staff Only: item control page