All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD6-S1-T4.1
Paper Title Trace Reconstruction with Bounded Edit Distance
Authors Jin Sima, Jehoshua Bruck, Calefornia Institute of Technology, United States
Session D6-S1-T4: Trace Reconstruction
Chaired Session: Monday, 19 July, 22:00 - 22:20
Engagement Session: Monday, 19 July, 22:20 - 22:40
Abstract The trace reconstruction problem studies the number of noisy samples needed to recover an unknown string $\boldx\in\{0,1\}^n$ with high probability, where the samples are independently obtained by passing $\boldx$ 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 $\boldx$ 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.