Lower bounds for trace reconstruction. (English) Zbl 1445.62014

Holden, Nina; Lyons, Russell

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.)

Keywords:

trace reconstruction problem; strings; deletion channel; sample complexity

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.