Trace Reconstruction: Generalized and Parameterized

Authors Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, Soumyabrata Pal



PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.68.pdf
  • Filesize: 0.58 MB
  • 25 pages

Document Identifiers

Author Details

Akshay Krishnamurthy
  • College of Information and Computer Sciences, University of Massachusetts, Amherst, USA
Arya Mazumdar
  • College of Information and Computer Sciences, University of Massachusetts, Amherst, USA
Andrew McGregor
  • College of Information and Computer Sciences, University of Massachusetts, Amherst, USA
Soumyabrata Pal
  • College of Information and Computer Sciences, University of Massachusetts, Amherst, USA

Cite AsGet BibTex

Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. Trace Reconstruction: Generalized and Parameterized. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 68:1-68:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.68

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. 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 super-logarithmic 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 k-sparse 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 k-sparse and we additionally have a "separation" promise, specifically that the indices of 1’s in x all differ by Omega(k log n).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Probability and statistics
Keywords
  • deletion channel
  • trace reconstruction
  • matrix reconstruction

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Dimitris Achlioptas and Frank McSherry. On spectral learning of mixtures of distributions. In Conference on Learning Theory, 2005. Google Scholar
  2. Sanjeev Arora and Ravi Kannan. Learning mixtures of arbitrary gaussians. In Symposium on Theory of Computing, 2001. Google Scholar
  3. Frank Ban, Xi Chen, Adam Frelich, Rocco A. Servedio, and Sandip Sinha. Beyond trace reconstruction: Population recovery from the deletion channel. arXiv, 2019. URL: http://arxiv.org/abs/1904.05532.
  4. Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. Reconstructing strings from random traces. In Symposium on Discrete Algorithms, 2004. Google Scholar
  5. Mikhail Belkin and Kaushik Sinha. Polynomial learning of distribution families. In Foundations of Computer Science, 2010. Google Scholar
  6. P. Borwein and T. Erdélyi. Littlewood-Type Problems on Subarcs of the Unit Circle. Indiana University Mathematics Journal, 1997. Google Scholar
  7. Siu-On Chan, Ilias Diakonikolas, Rocco A Servedio, and Xiaorui Sun. Learning mixtures of structured distributions over discrete domains. In Symposium on Discrete Algorithms, 2013. Google Scholar
  8. Mahdi Cheraghchi, Ryan Gabrys, Olgica Milenkovic, and João Ribeiro. Coded trace reconstruction. arXiv e-prints, page arXiv:1903.09992, March 2019. URL: http://arxiv.org/abs/1903.09992.
  9. Sanjoy Dasgupta. Learning mixtures of Gaussians. In Foundations of Computer Science, 1999. Google Scholar
  10. Sami Davies, Miklos Z. Racz, and Cyrus Rashtchian. Reconstructing Trees from Traces. arXiv e-prints, page arXiv:1902.05101, February 2019. URL: http://arxiv.org/abs/1902.05101.
  11. Anindya De, Ryan O'Donnell, and Rocco A. Servedio. Optimal mean-based algorithms for trace reconstruction. In Symposium on Theory of Computing, 2017. Google Scholar
  12. Jon Feldman, Ryan O'Donnell, and Rocco A Servedio. Learning mixtures of product distributions over discrete domains. SIAM Journal on Computing, 2008. Google Scholar
  13. Anna C. Gilbert and Piotr Indyk. Sparse Recovery Using Sparse Matrices. Proceedings of the IEEE, 2010. Google Scholar
  14. Moritz Hardt and Eric Price. Tight bounds for learning a mixture of two gaussians. In Symposium on Theory of Computing, 2015. Google Scholar
  15. Lisa Hartung, Nina Holden, and Yuval Peres. Trace reconstruction with varying deletion probabilities. In Workshop on Analytic Algorithmics and Combinatorics, 2018. Google Scholar
  16. Nina Holden and Russell Lyons. Lower bounds for trace reconstruction. arXiv, 2018. URL: http://arxiv.org/abs/1808.02336.
  17. Nina Holden, Robin Pemantle, and Yuval Peres. Subpolynomial trace reconstruction for random strings and arbitrary deletion probability. In Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018., pages 1799-1840, 2018. Google Scholar
  18. Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder. Trace reconstruction with constant deletion probability and related results. In Symposium on Discrete Algorithms, 2008. Google Scholar
  19. Samuel B Hopkins and Jerry Li. Mixture models, robustness, and sum of squares proofs. In Symposium on Theory of Computing, 2018. Google Scholar
  20. Adam Tauman Kalai, Ankur Moitra, and Gregory Valiant. Efficiently learning mixtures of two Gaussians. In Symposium on Theory of Computing, 2010. Google Scholar
  21. Sampath Kannan and Andrew McGregor. More on Reconstructing Strings from Random Traces: Insertions and Deletions. In International Symposium on Information Theory, 2005. Google Scholar
  22. Géza Kós, Péter Ligeti, and Péter Sziklai. Reconstruction of matrices from submatrices. Mathematics of Computation, 2009. URL: https://doi.org/10.1090/S0025-5718-09-02210-8.
  23. I. Krasikov and Y. Roditty. On a Reconstruction Problem for Sequences. Journal of Combinatorial Theory, Series A, 1997. Google Scholar
  24. Andrew McGregor, Eric Price, and Sofya Vorotnikova. Trace Reconstruction Revisited. In European Symposium on Algorithms, 2014. Google Scholar
  25. Ankur Moitra and Gregory Valiant. Settling the polynomial learnability of mixtures of gaussians. In Foundations of Computer Science, 2010. Google Scholar
  26. Fedor Nazarov and Yuval Peres. Trace reconstruction with exp(O(n^1/3) samples. In Symposium on Theory of Computing, 2017. Google Scholar
  27. Yuval Peres and Alex Zhai. Average-Case Reconstruction for the Deletion Channel: Subpolynomially Many Traces Suffice. In Symposium on Foundations of Computer Science, 2017. Google Scholar
  28. Krishnamurthy Viswanathan and Ram Swaminathan. Improved string reconstruction over insertion-deletion channels. In Symposium on Discrete Algorithms, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail