Lower bounds for trace reconstruction

DOI10.1214/19-AAP1506zbMath1445.62014arXiv1808.02336MaRDI QIDQ2192732

Russell Lyons, Nina Holden

Publication date: 17 August 2020

Published in: The Annals of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

stringsdeletion channelsample complexitytrace reconstruction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Minimax procedures in statistical decision theory (62C20) Applications of queueing theory (congestion, allocation, storage, traffic, etc.) (60K30) Algorithms on strings (68W32) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (8)

Tree trace reconstruction using subtraces ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Hidden words statistics for large patterns ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• DNA approach to scenery reconstruction
• Approximate distributions of order statistics. With applications to nonparametric statistics
• Distinguishing sceneries by observing the scenery along a random walk path
• Reconstructing a piece of scenery with polynomially many observations.
• Information recovery from observations by a random walk having jump distribution with exponential tails
• Trace Reconstruction Revisited
• Finding blocks and other patterns in a random coloring of ℤ
• Trace reconstruction with exp(O(n ^1/3 )) samples
• Optimal mean-based algorithms for trace reconstruction
• Introduction to nonparametric estimation

This page was built for publication: Lower bounds for trace reconstruction