Approximate Trace Reconstruction via Median String (In Average-Case)

Diptarka Chakraborty, Debarati Das, Robert Krauthgamer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We consider an approximate version of the trace reconstruction problem, where the goal is to recover an unknown string s ∈ {0, 1}n from m traces (each trace is generated independently by passing s through a probabilistic insertion-deletion channel with rate p). We present a deterministic near-linear time algorithm for the average-case model, where s is random, that uses only three traces. It runs in near-linear time Õ(n) and with high probability reports a string within edit distance Õ(p2n) from s, which significantly improves over the straightforward bound of O(pn). Technically, our algorithm computes a (1 + ϵ)-approximate median of the three input traces. To prove its correctness, our probabilistic analysis shows that an approximate median is indeed close to the unknown s. To achieve a near-linear time bound, we have to bypass the well-known dynamic programming algorithm that computes an optimal median in time O(n3).

Original languageEnglish (US)
Title of host publication41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021
EditorsMikolaj Bojanczyk, Chandra Chekuri
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772150
DOIs
StatePublished - Dec 1 2021
Event41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021 - Virtual, Online
Duration: Dec 15 2021Dec 17 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume213
ISSN (Print)1868-8969

Conference

Conference41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2021
CityVirtual, Online
Period12/15/2112/17/21

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint

Dive into the research topics of 'Approximate Trace Reconstruction via Median String (In Average-Case)'. Together they form a unique fingerprint.

Cite this