Subpolynomial trace reconstruction for random strings and arbitrary deletion probability

DOI10.4171/MSL/16zbMath1472.68223arXiv1801.04783OpenAlexW3158992927MaRDI QIDQ2035747

Nina Holden, Yuval Peres, Alex Zhai, Robin Pemantle

Publication date: 25 June 2021

Published in: Mathematical Statistics and Learning (Search for Journal in Brave)

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

zbMATH Keywords

deletion channeltrace reconstruction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Sums of independent random variables; random walks (60G50) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Channel models (including quantum) in information and communication theory (94A40) Algorithms on strings (68W32) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (6)

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

Cites Work

• Unnamed Item
• Unnamed Item
• A survey of results for deletion channels and related synchronization channels
• Lower bounds for trace reconstruction
• Trace Reconstruction Revisited
• Littlewood-type problems on subarcs of the unit circle
• Efficient reconstruction of sequences
• Trace reconstruction with exp(O(n ^1/3 )) samples
• Optimal mean-based algorithms for trace reconstruction
• Efficient reconstruction of sequences from their subsequences of supersequences

This page was built for publication: Subpolynomial trace reconstruction for random strings and arbitrary deletion probability