Optimal mean-based algorithms for trace reconstruction

DOI10.1145/3055399.3055450zbMATH Open1369.68202arXiv1612.03148OpenAlexW2565322834MaRDI QIDQ4978045FDOQ4978045

Rocco A. Servedio, Ryan O'Donnell, Anindya De

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: In the (deletion-channel) trace reconstruction problem, there is an unknown $n$-bit source string $x$. An algorithm is given access to independent traces of $x$, where a trace is formed by deleting each bit of~$x$ independently with probability~$delta$. The goal of the algorithm is to recover~$x$ exactly (with high probability), while minimizing samples (number of traces) and running time. Previously, the best known algorithm for the trace reconstruction problem was due to Holenstein~et~al.; it uses $exp(ildeO(n^{1/2}))$ samples and running time for any fixed $0<delta<1$. It is also what we call a "mean-based algorithm", meaning that it only uses the empirical means of the individual bits of the traces. Holenstein~et~al.~also gave a lower bound, showing that any mean-based algorithm must use at least $n^{ildeOmega(logn)}$ samples. In this paper we improve both of these results, obtaining matching upper and lower bounds for mean-based trace reconstruction. For any constant deletion rate $0<delta<1$, we give a mean-based algorithm that uses $exp(O(n^{1/3}))$ time and traces; we also prove that any mean-based algorithm must use at least $exp(Omega(n^{1/3}))$ traces. In fact, we obtain matching upper and lower bounds even for $delta$ subconstant and $ho:=1-delta$ subconstant: when $(lo{g}^{3}n)/nlldeltaleq1/2$ the bound is $exp(-Theta(deltan{)}^{1/3})$, and when $1/sqrtnllholeq1/2$ the bound is $exp(-Theta(n/ho{)}^{1/3})$. Our proofs involve estimates for the maxima of Littlewood polynomials on complex disks. We show that these techniques can also be used to perform trace reconstruction with random insertions and bit-flips in addition to deletions. We also find a surprising result: for deletion probabilities $delta>1/2$, the presence of insertions can actually help with trace reconstruction.

Full work available at URL: https://arxiv.org/abs/1612.03148

zbMATH Keywords

Littlewood polynomialsdeletion channeltrace reconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cited In (12)

• Title not available (Why is that?)
• Title not available (Why is that?)
• An optimal endpoint trace embedding
• Tree trace reconstruction using subtraces
• Optimal mean-based algorithms for trace reconstruction
• Lower bounds for trace reconstruction
• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• Improved Variants of the Hutch++ Algorithm for Trace Estimation
• New lower bounds for trace reconstruction
• Information-Theoretic Foundations of DNA Data Storage
• Reconstructing trees from traces
• The trace reconstruction problem for spider graphs

This page was built for publication: Optimal mean-based algorithms for trace reconstruction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978045)