New lower bounds for trace reconstruction

DOI10.1214/20-AIHP1089zbMath1469.62189arXiv1905.03031MaRDI QIDQ2041812

Zachary Chase

Publication date: 23 July 2021

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Algebraic statistics (62R01)

Related Items (4)

Tree trace reconstruction using subtraces ⋮ Reconstructing trees from traces ⋮ The trace reconstruction problem for spider graphs ⋮ Information-Theoretic Foundations of DNA Data Storage

Cites Work

• Unnamed Item
• Unnamed Item
• Computational excursions in analysis and number theory
• Reconstruction from subsequences.
• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• Lower bounds for trace reconstruction
• Generalized phase retrieval: measurement number, matrix recovery and beyond
• Trace reconstruction with exp(O(n ^1/3 )) samples
• Optimal mean-based algorithms for trace reconstruction
• Coded Trace Reconstruction

This page was built for publication: New lower bounds for trace reconstruction