Lower bounds for trace reconstruction
From MaRDI portal
Publication:2192732
DOI10.1214/19-AAP1506zbMath1445.62014arXiv1808.02336MaRDI QIDQ2192732
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
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