Trace reconstruction with exp(O(n 1/3 )) samples

DOI10.1145/3055399.3055494zbMath1370.68087arXiv1612.03599OpenAlexW2564763601MaRDI QIDQ4978044

Yuval Peres, F. L. Nazarov

Publication date: 17 August 2017

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

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

zbMATH Keywords

generating functionreconstructionLittlewood polynomialdeletion channelsample complexity

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)

Related Items (10)

Tree trace reconstruction using subtraces ⋮ Lower bounds for trace reconstruction ⋮ Unnamed Item ⋮ Optimal mean-based algorithms for trace reconstruction ⋮ Unnamed Item ⋮ Subpolynomial trace reconstruction for random strings and arbitrary deletion probability ⋮ New lower bounds for trace reconstruction ⋮ Reconstructing trees from traces ⋮ The trace reconstruction problem for spider graphs ⋮ Information-Theoretic Foundations of DNA Data Storage

This page was built for publication: Trace reconstruction with exp(O(n ^1/3 )) samples