Trace Reconstruction: Generalized and Parameterized

DOI10.1109/TIT.2021.3066010MaRDI QIDQ5001712zbMATH OpenOpenAlexFDO

Authors A. Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal

Publication date 23 July 2021

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

random matrix reconstructionreconstruction of unknown binary string given random traces

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: In the beautifully simple-to-state problem of trace reconstruction, the goal is to reconstruct an unknown binary string $x$ given random "traces" of $x$ where each trace is generated by deleting each coordinate of $x$ independently with probability $p<1$. The problem is well studied both when the unknown string is arbitrary and when it is chosen uniformly at random. For both settings, there is still an exponential gap between upper and lower sample complexity bounds and our understanding of the problem is still surprisingly limited. In this paper, we consider natural parameterizations and generalizations of this problem in an effort to attain a deeper and more comprehensive understanding. We prove that $exp(O(n^{1/4}sqrtlogn))$ traces suffice for reconstructing arbitrary matrices. In the matrix version of the problem, each row and column of an unknown $sqrtnimessqrtn$ matrix is deleted independently with probability $p$. Our results contrasts with the best known results for sequence reconstruction where the best known upper bound is $exp(O(n^{1/3}))$. An optimal result for random matrix reconstruction: we show that $Theta(logn)$ traces are necessary and sufficient. This is in contrast to the problem for random sequences where there is a super-logarithmic lower bound and the best known upper bound is $exp(O(lo{g}^{1/3}n))$. We show that $exp(O(k^{1/3}lo{g}^{2/3}n))$ traces suffice to reconstruct $k$-sparse strings, providing an improvement over the best known sequence reconstruction results when $k=o(n/lo{g}^{2}n)$. We show that $extrmpoly(n)$ traces suffice if $x$ is $k$-sparse and we additionally have a "separation" promise, specifically that the indices of 1's in $x$ all differ by $Omega(klogn)$.

Cited in

(7)

• Reconstructing trees from traces
• The trace reconstruction problem for spider graphs
• Lower bounds for trace reconstruction
• scientific article; zbMATH DE number 936308 (Why is no real title available?)
• scientific article; zbMATH DE number 7650111 (Why is no real title available?)
• Near-optimal trace reconstruction for mildly separated strings
• An optimal endpoint trace embedding

This page was built for publication: Trace Reconstruction: Generalized and Parameterized

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