##
**Lower bounds for trace reconstruction.**
*(English)*
Zbl 1445.62014

Ann. Appl. Probab. 30, No. 2, 503-525 (2020); erratum ibid. 32, No. 4, 3201-3203 (2022).

Summary: In the trace reconstruction problem, an unknown bit string \(\mathbf{x} \in \{0, 1\}^n\) is sent through a deletion channel where each bit is deleted independently with some probability \(q \in (0, 1)\), yielding a contracted string \(\widetilde{\mathbf{x}}\). How many i.i.d. samples of \({\widetilde{\mathbf{x}}}\) are needed to reconstruct \(\mathbf{x}\) with high probability? We prove that there exist \(\mathbf{x}, \mathbf{y}\in \{0,1\}^n\) such that at least \(cn^{5/4}/\sqrt{\log n}\) traces are required to distinguish between \(\mathbf{x}\) and \(\mathbf{y}\) for some absolute constant \(c\), improving the previous lower bound of \(cn\). Furthermore, our result improves the previously known lower bound for reconstruction of random strings from \(c\log^2n\) to \(c\log^{9/4}n/\sqrt{\log\log n}\).

### MSC:

62C20 | Minimax procedures in statistical decision theory |

68Q25 | Analysis of algorithms and problem complexity |

68W32 | Algorithms on strings |

68W40 | Analysis of algorithms |

68Q87 | Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) |

60K30 | Applications of queueing theory (congestion, allocation, storage, traffic, etc.) |

PDFBibTeX
XMLCite

\textit{N. Holden} and \textit{R. Lyons}, Ann. Appl. Probab. 30, No. 2, 503--525 (2020; Zbl 1445.62014)

### References:

[1] | Batu, T., Kannan, S., Khanna, S. and McGregor, A. (2004). Reconstructing strings from random traces. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms 910-918. ACM, New York. · Zbl 1318.68206 |

[2] | Benjamini, I. and Kesten, H. (1996). Distinguishing sceneries by observing the scenery along a random walk path. J. Anal. Math. 69 97-135. · Zbl 0868.60059 · doi:10.1007/BF02787104 |

[3] | Chase, Z. (2019). New lower bounds for trace reconstruction. Available at arXiv:1905.03031. |

[4] | Combes, R. (2015). An extension of McDiarmid’s inequality. Available at arXiv:1511.05240. |

[5] | De, A., O’Donnell, R. and Servedio, R. A. (2017). Optimal mean-based algorithms for trace reconstruction. In STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing 1047-1056. ACM, New York. · Zbl 1369.68202 |

[6] | Hart, A., Machado, F. and Matzinger, H. (2015). Information recovery from observations by a random walk having jump distribution with exponential tails. Markov Process. Related Fields 21 939-970. · Zbl 1342.60065 |

[7] | Holden, N., Pemantle, R. and Peres, Y. (2018). Subpolynomial trace reconstruction for random strings and arbitrary deletion probability. In Proceedings of the 31st Conference on Learning Theory (S. S. Bubeck, V. V. Perchet and P. P. Rigollet, eds.). Proceedings of Machine Learning Research 75 1799-1840. |

[8] | Holenstein, T., Mitzenmacher, M., Panigrahy, R. and Wieder, U. (2008). Trace reconstruction with constant deletion probability and related results. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms 389-398. ACM, New York. · Zbl 1192.94064 |

[9] | Liggett, T. M. (2002). Tagged particle distributions or how to choose a head at random. In In and Out of Equilibrium (Mambucaba, 2000). Progress in Probability 51 133-162. Birkhäuser, Boston, MA. · Zbl 1108.60319 |

[10] | Matzinger, H. and Pinzon, A. P. (2011). DNA approach to scenery reconstruction. Stochastic Process. Appl. 121 2455-2473. · Zbl 1227.60114 · doi:10.1016/j.spa.2011.04.010 |

[11] | Matzinger, H. and Rolles, S. W. W. (2003). Reconstructing a piece of scenery with polynomially many observations. Stochastic Process. Appl. 107 289-300. · Zbl 1075.60521 · doi:10.1016/S0304-4149(03)00085-1 |

[12] | Matzinger, H. and Rolles, S. W. W. (2006). Finding blocks and other patterns in a random coloring of \(\Bbb{Z} \). Random Structures Algorithms 28 37-75. · Zbl 1086.60067 · doi:10.1002/rsa.20110 |

[13] | McGregor, A., Price, E. and Vorotnikova, S. (2014). Trace reconstruction revisited. In Algorithms—ESA 2014. Lecture Notes in Computer Science 8737 689-700. Springer, Heidelberg. · Zbl 1425.68470 |

[14] | Nazarov, F. and Peres, Y. (2017). Trace reconstruction with \(\exp(O(n^{1/3}))\) samples. In STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing 1042-1046. ACM, New York. · Zbl 1370.68087 |

[15] | Peres, Y. and Zhai, A. (2017). Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice. In 58th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2017 228-239. IEEE Computer Soc., Los Alamitos, CA. |

[16] | Reiss, R.-D. (1989). Approximate Distributions of Order Statistics: With Applications to Nonparametric Statistics. Springer Series in Statistics. Springer, New York. · Zbl 0682.62009 |

[17] | Tsybakov, A. B. (2009). Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York. · Zbl 1176.62032 |

[18] | Yao, A. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.