Near-optimal trace reconstruction for mildly separated strings

DOI10.4230/LIPICS.ICALP.2025.3MaRDI QIDQ7346430zbMATH OpenFDO

Authors Anders Aamand, Allen Liu, Shyam Narayanan

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.3

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• Average-case reconstruction for the deletion channel: subpolynomially many traces suffice
• Average-case to (shifted) worst-case reduction for the trace reconstruction problem
• Beyond trace reconstruction: population recovery from the deletion channel
• Coded Trace Reconstruction
• Efficient reconstruction of sequences
• Efficient reconstruction of sequences from their subsequences of supersequences
• Graph reconstruction from random subgraphs
• scientific article; zbMATH DE number 5764889 (Why is no real title available?)
• scientific article; zbMATH DE number 5764890 (Why is no real title available?)
• scientific article; zbMATH DE number 7650111 (Why is no real title available?)
• scientific article; zbMATH DE number 7788415 (Why is no real title available?)
• scientific article; zbMATH DE number 7799589 (Why is no real title available?)
• Lower bounds for trace reconstruction
• New lower bounds for trace reconstruction
• Optimal mean-based algorithms for trace reconstruction
• Reconstructing strings from random traces
• Separating words and trace reconstruction
• The trace reconstruction problem for spider graphs
• Trace reconstruction revisited
• Trace reconstruction with \(\exp(O(n^{1/3}))\) samples
• Trace reconstruction with varying deletion probabilities
• Trace Reconstruction: Generalized and Parameterized

This page was built for publication: Near-optimal trace reconstruction for mildly separated strings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346430)