{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:08:34Z","timestamp":1779174514173,"version":"3.51.4"},"reference-count":43,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T00:00:00Z","timestamp":1773100800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2026,5]]},"abstract":"Abstract<\/jats:title>\n \n A\n trace<\/jats:italic>\n of a sequence is generated by deleting each bit of the sequence independently with a fixed probability. The well-studied\n trace reconstruction<\/jats:italic>\n problem asks how many traces are required to reconstruct an unknown binary sequence with high probability. In this paper, we study the multidimensional version of this problem for matrices and hypermatrices, where a trace is generated by deleting each row\/column of the matrix or each slice of the hypermatrix independently with a constant probability. Previously, Krishnamurthy, Mazumdar, McGregor and Pal showed that\n \n \n \n exp left parenthesis ModifyingAbove upper O With tilde left parenthesis n Superscript d divided by left parenthesis d plus 2 right parenthesis Baseline right parenthesis right parenthesis<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n exp<\/mml:mi>\n \u2061<\/mml:mo>\n (<\/mml:mo>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n <\/mml:mrow>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n d<\/mml:mi>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n (<\/mml:mo>\n d<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:math>\n $\\exp (\\widetilde {O}(n^{d\/(d+2)}))$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n traces suffice to reconstruct any unknown\n \n \n \n n times n<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n n<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:math>\n $n\\times n$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n matrix (for\n \n \n \n d equals 2<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n d<\/mml:mi>\n =<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:math>\n $d=2$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ) and any unknown\n \n \n \n n Superscript times d<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n \n n<\/mml:mi>\n \n \u00d7<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n $n^{\\times d}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n hypermatrix. By developing a dimension reduction procedure and establishing a multivariate version of the Littlewood-type result that lower bounds sparse complex polynomials around\n \n \n \n 1<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n 1<\/mml:mn>\n <\/mml:math>\n $1$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , we improve this upper bound by showing that\n \n \n \n exp left parenthesis ModifyingAbove upper O With tilde left parenthesis n Superscript 3 divided by 7 Baseline right parenthesis right parenthesis<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n exp<\/mml:mi>\n \u2061<\/mml:mo>\n (<\/mml:mo>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n <\/mml:mrow>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 7<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:math>\n $\\exp (\\widetilde {O}(n^{3\/7}))$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n traces suffice to reconstruct any unknown\n \n \n \n n times n<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n n<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:math>\n $n\\times n$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n matrix, and\n \n \n \n exp left parenthesis ModifyingAbove upper O With tilde left parenthesis n Superscript 3 divided by 5 Baseline right parenthesis right parenthesis<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n exp<\/mml:mi>\n \u2061<\/mml:mo>\n (<\/mml:mo>\n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n <\/mml:mrow>\n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 3<\/mml:mn>\n \n \/<\/mml:mo>\n <\/mml:mrow>\n 5<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:math>\n $\\exp (\\widetilde {O}(n^{3\/5}))$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n traces suffice to reconstruct any unknown\n \n \n \n n Superscript times d<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n \n n<\/mml:mi>\n \n \u00d7<\/mml:mo>\n d<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n $n^{\\times d}$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n hypermatrix. In contrast to the earlier bound, our new exponent is bounded away from\n \n \n \n 1<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n 1<\/mml:mn>\n <\/mml:math>\n $1$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n even as\n \n \n \n d<\/jats:alt-text>\n <\/jats:inline-graphic>\n \n d<\/mml:mi>\n <\/mml:math>\n $d$<\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n becomes very large.\n <\/jats:p>","DOI":"10.1017\/s0963548326100364","type":"journal-article","created":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T06:17:46Z","timestamp":1773123466000},"page":"356-374","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["Trace reconstruction of matrices and hypermatrices"],"prefix":"10.1017","volume":"35","author":[{"given":"Wenjie","family":"Zhong","sequence":"first","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04c4dkn09","id-type":"ROR","asserted-by":"publisher"}],"name":"School of Mathematical Sciences, University of Science and Technology of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiande","family":"Zhang","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04c4dkn09","id-type":"ROR","asserted-by":"publisher"}],"name":"School of Mathematical Sciences, University of Science and Technology of China"},{"name":"Hefei National Laboratory, University of Science and Technology of China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2026,3,10]]},"reference":[{"key":"S0963548326100364_ref40","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.29"},{"key":"S0963548326100364_ref16","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055450"},{"key":"S0963548326100364_ref31","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316669846"},{"key":"S0963548326100364_ref41","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90215-9"},{"key":"S0963548326100364_ref25","first-page":"56","article-title":"The reconstruction of a word from fragments","volume":"4","author":"Kalashnik","year":"1973","journal-title":"Numer. Math. Comput. Technol."},{"key":"S0963548326100364_ref2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2019)","author":"Ban","year":"2019"},{"key":"S0963548326100364_ref37","unstructured":"[37] Narayanan, S. and Ren, M. (2021) Circular trace reconstruction. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)."},{"key":"S0963548326100364_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2800044"},{"key":"S0963548326100364_ref34","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3081"},{"key":"S0963548326100364_ref27","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-09-02210-8"},{"key":"S0963548326100364_ref22","doi-asserted-by":"publisher","DOI":"10.1214\/19-AAP1506"},{"key":"S0963548326100364_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/21-AAP1662"},{"key":"S0963548326100364_ref18","doi-asserted-by":"publisher","DOI":"10.4310\/MAA.2000.v7.n4.a1"},{"key":"S0963548326100364_ref12","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451118"},{"key":"S0963548326100364_ref39","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1970.11992413"},{"key":"S0963548326100364_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/S0097-3165(03)00103-1"},{"key":"S0963548326100364_ref9","unstructured":"[9] Chase, Z. (2020) New upper bounds for trace reconstruction. arXiv preprint arXiv: 2009.03296."},{"key":"S0963548326100364_ref32","first-page":"593","article-title":"Reconstruction of objects from the minimum number of distorted patterns","volume":"354","author":"Levenshtein","year":"1997","journal-title":"Dokl. Akad. Nauk"},{"key":"S0963548326100364_ref36","unstructured":"[36] Narayanan, S. (2020) Population recovery from the deletion channel: nearly matching trace reconstruction bounds. arXiv preprint arXiv: 2004.06828."},{"key":"S0963548326100364_ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2996377"},{"key":"S0963548326100364_ref23","doi-asserted-by":"publisher","DOI":"10.4171\/msl\/16"},{"key":"S0963548326100364_ref42","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2023.3260872"},{"key":"S0963548326100364_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00052"},{"key":"S0963548326100364_ref24","doi-asserted-by":"crossref","unstructured":"[24] 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 (SODA), pp. 389\u2013398.","DOI":"10.1137\/1.9780898716474"},{"key":"S0963548326100364_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190140102"},{"key":"S0963548326100364_ref43","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2024.105966"},{"key":"S0963548326100364_ref1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00050"},{"key":"S0963548326100364_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190010306"},{"key":"S0963548326100364_ref20","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22616"},{"key":"S0963548326100364_ref7","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611599011831"},{"key":"S0963548326100364_ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_57"},{"key":"S0963548326100364_ref30","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3066010"},{"key":"S0963548326100364_ref3","unstructured":"[3] 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 (SODA), pp. 910\u2013918."},{"key":"S0963548326100364_ref29","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2732"},{"key":"S0963548326100364_ref6","first-page":"1323","article-title":"Littlewood-type problems on subarcs of the unit circle","author":"Borwein","year":"1997","journal-title":"Indiana Univer. Math. J."},{"key":"S0963548326100364_ref28","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2983678"},{"key":"S0963548326100364_ref33","doi-asserted-by":"publisher","DOI":"10.1109\/18.904499"},{"key":"S0963548326100364_ref14","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9517926"},{"key":"S0963548326100364_ref11","first-page":"627","article-title":"New lower bounds for trace reconstruction","volume":"57","author":"Chase","year":"2021","journal-title":"Ann. l\u2019Inst. Henri Poincar\u00e9-Probab. Stat."},{"key":"S0963548326100364_ref26","unstructured":"[26] Konstantinova, E. , Levenshtein, V. and Siemons, J. (2007) Reconstruction of permutations distorted by single transposition errors. arXiv preprint arXiv:math\/0702191."},{"key":"S0963548326100364_ref10","unstructured":"[10] Chase, Z. and Peres, Y. (2021) Approximate trace reconstruction of random strings from a constant number of traces. arXiv preprint arXiv:2107.06454."},{"key":"S0963548326100364_ref38","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055494"},{"key":"S0963548326100364_ref21","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548326100364","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T06:13:06Z","timestamp":1779171186000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548326100364\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,10]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["S0963548326100364"],"URL":"https:\/\/doi.org\/10.1017\/s0963548326100364","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,10]]},"assertion":[{"value":"\u00a9 The Author(s), 2026. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}