Trace reconstruction with exp(O(n 1/3 )) samples
From MaRDI portal
Publication:4978044
DOI10.1145/3055399.3055494zbMath1370.68087arXiv1612.03599OpenAlexW2564763601MaRDI QIDQ4978044
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
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