Krishnamurthy, Akshay ;
Mazumdar, Arya ;
McGregor, Andrew ;
Pal, Soumyabrata
Trace Reconstruction: Generalized and Parameterized
Abstract
In the beautifully simpletostate 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. Perhaps our most surprising results are:
1) We prove that exp(O(n^(1/4) sqrt{log n})) traces suffice for reconstructing arbitrary matrices. In the matrix version of the problem, each row and column of an unknown sqrt{n} x sqrt{n} 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))).
2) An optimal result for random matrix reconstruction: we show that Theta(log n) traces are necessary and sufficient. This is in contrast to the problem for random sequences where there is a superlogarithmic lower bound and the best known upper bound is exp({O}(log^(1/3) n)).
3) We show that exp(O(k^(1/3) log^(2/3) n)) traces suffice to reconstruct ksparse strings, providing an improvement over the best known sequence reconstruction results when k = o(n/log^2 n).
4) We show that poly(n) traces suffice if x is ksparse and we additionally have a "separation" promise, specifically that the indices of 1's in x all differ by Omega(k log n).
BibTeX  Entry
@InProceedings{krishnamurthy_et_al:LIPIcs:2019:11189,
author = {Akshay Krishnamurthy and Arya Mazumdar and Andrew McGregor and Soumyabrata Pal},
title = {{Trace Reconstruction: Generalized and Parameterized}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {68:168:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11189},
URN = {urn:nbn:de:0030drops111891},
doi = {10.4230/LIPIcs.ESA.2019.68},
annote = {Keywords: deletion channel, trace reconstruction, matrix reconstruction}
}
06.09.2019
Keywords: 

deletion channel, trace reconstruction, matrix reconstruction 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 