The trace reconstruction problem for spider graphs

DOI10.1016/j.disc.2022.113115OpenAlexW4296556002MaRDI QIDQ2092331

William Yue, Alec Sun

Publication date: 2 November 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsLittlewood polynomialstrace reconstruction

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Theory of computing (68Qxx) Algorithms on strings (68W32)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global alignment of molecular sequences via ancestral state reconstruction
• Reconstruction of objects from a minimum number of distorted patterns
• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• New lower bounds for trace reconstruction
• Lower bounds for trace reconstruction
• Trace Reconstruction Revisited
• Trace reconstruction with exp(O(n ^1/3 )) samples
• Optimal mean-based algorithms for trace reconstruction
• Trace Reconstruction: Generalized and Parameterized
• Trace Reconstruction Problems in Computational Biology
• Coded Trace Reconstruction
• Trace reconstruction with varying deletion probabilities

This page was built for publication: The trace reconstruction problem for spider graphs