{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T18:45:07Z","timestamp":1754160307728,"version":"3.41.2"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"NSF","award":["CCF-1703925 and IIS-1838154"],"award-info":[{"award-number":["CCF-1703925 and IIS-1838154"]}]},{"name":"NSF","award":["CCF-1926872 and CCF-1910534"],"award-info":[{"award-number":["CCF-1926872 and CCF-1910534"]}]},{"DOI":"10.13039\/501100001692","name":"Croucher Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001692","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Simons Collaboration on Algorithms and Geometry"},{"name":"NSF","award":["CCF-1814873, IIS-1838154, CCF-1563155"],"award-info":[{"award-number":["CCF-1814873, IIS-1838154, CCF-1563155"]}]},{"name":"Simons Collaboration on Algorithms and Geometry"},{"name":"NSF","award":["CCF-1714818, CCF-1822809, IIS-1838154, CCF-1617955, CCF-1740833"],"award-info":[{"award-number":["CCF-1714818, CCF-1822809, IIS-1838154, CCF-1617955, CCF-1740833"]}]},{"name":"Simons Collaboration on Algorithms and Geometry"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2025,7,31]]},"abstract":"\n In the\n trace reconstruction problem<\/jats:italic>\n , an unknown source string\n x<\/jats:italic>\n \u2208 {0,1}\n \n n<\/jats:italic>\n <\/jats:sup>\n is sent through a probabilistic\n deletion channel<\/jats:italic>\n that independently deletes each bit with probability \u03b4 and concatenates the surviving bits, yielding a\n trace<\/jats:italic>\n of\n x<\/jats:italic>\n . The problem is to reconstruct\n x<\/jats:italic>\n given independent traces. This problem has received much attention in recent years both in the worst-case setting where\n x<\/jats:italic>\n may be an arbitrary string in {0,1}\n \n n<\/jats:italic>\n <\/jats:sup>\n [\n 7<\/jats:xref>\n ,\n 8<\/jats:xref>\n ,\n 10<\/jats:xref>\n ,\n 11<\/jats:xref>\n ,\n 12<\/jats:xref>\n ,\n 23<\/jats:xref>\n ] and in the average-case setting where\n x<\/jats:italic>\n is drawn uniformly at random from {0,1}\n \n n<\/jats:italic>\n <\/jats:sup>\n [\n 7<\/jats:xref>\n ,\n 8<\/jats:xref>\n ,\n 12<\/jats:xref>\n ,\n 13<\/jats:xref>\n ,\n 25<\/jats:xref>\n ].\n <\/jats:p>\n \n This article studies trace reconstruction in the\n smoothed analysis<\/jats:italic>\n setting, in which a \u201cworst-case\u201d string\n x<\/jats:italic>\n worst<\/jats:sup>\n is chosen arbitrarily from {0,1}\n \n n<\/jats:italic>\n <\/jats:sup>\n , and then a perturbed version\n \n x<\/jats:italic>\n <\/jats:bold>\n of\n x<\/jats:italic>\n worst<\/jats:sup>\n is formed by independently replacing each coordinate by a uniform random bit with probability \u03c3. The problem is to reconstruct\n \n x<\/jats:italic>\n <\/jats:bold>\n given independent traces from it.\n <\/jats:p>\n \n Our main result is an algorithm that, for any constant perturbation rate 0< \u03c3 < 1 and any constant deletion rate 0 < \u03b4 < 1, uses poly(\n n<\/jats:italic>\n ) running time and traces and succeeds with high probability in reconstructing the string\n \n x<\/jats:italic>\n <\/jats:bold>\n . This stands in contrast with the worst-case version of the problem, for which\n \n \\(\\text{exp}(\\tilde{O}(n^{1\/5}))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the best known time and sample complexity [\n 8<\/jats:xref>\n ].\n <\/jats:p>\n \n Our approach is based on reconstructing\n \n x<\/jats:italic>\n <\/jats:bold>\n from the multiset of its short subwords and is quite different from previous algorithms for either the worst-case or average-case versions of the problem. The heart of our work is a new poly(\n n<\/jats:italic>\n )-time procedure for reconstructing the multiset of all\n O<\/jats:italic>\n (log\n n<\/jats:italic>\n )-length subwords of any source string\n x<\/jats:italic>\n \u2208 {0,1}\n \n n<\/jats:italic>\n <\/jats:sup>\n given access to traces of\n x<\/jats:italic>\n .\n <\/jats:p>","DOI":"10.1145\/3560819","type":"journal-article","created":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T08:38:07Z","timestamp":1661935087000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Polynomial-time Trace Reconstruction in the Smoothed Complexity Model"],"prefix":"10.1145","volume":"21","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5661-515X","authenticated-orcid":false,"given":"Xi","family":"Chen","sequence":"first","affiliation":[{"name":"Columbia University","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6795-8211","authenticated-orcid":false,"given":"Anindya","family":"De","sequence":"additional","affiliation":[{"name":"University of Pennsylvania","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5072-8110","authenticated-orcid":false,"given":"Chin Ho","family":"Lee","sequence":"additional","affiliation":[{"name":"Harvard University","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2407-543X","authenticated-orcid":false,"given":"Rocco","family":"Servedio","sequence":"additional","affiliation":[{"name":"Columbia University","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2592-175X","authenticated-orcid":false,"given":"Sandip","family":"Sinha","sequence":"additional","affiliation":[{"name":"Columbia University","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,7,26]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Complex Analysis. An Introduction to the Theory of Analytic Functions of One Complex Variable","author":"Ahlfors Lars V.","year":"1979","unstructured":"Lars V. Ahlfors. 1979. Complex Analysis. An Introduction to the Theory of Analytic Functions of One Complex Variable. McGraw-Hill."},{"key":"e_1_3_2_3_2","first-page":"745","volume-title":"Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS)","author":"Ban Frank","year":"2019","unstructured":"Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, and Sandip Sinha. 2019. Beyond trace reconstruction: Population recovery from the deletion channel. In Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 745\u2013768."},{"key":"e_1_3_2_4_2","first-page":"44:1\u201344:18","volume-title":"APPROX\/RANDOM 2019 (LIPIcs)","author":"Ban Frank","year":"2019","unstructured":"Frank Ban, Xi Chen, Rocco A. Servedio, and Sandip Sinha. 2019. Efficient average-case population recovery in the presence of insertions and deletions. In APPROX\/RANDOM 2019 (LIPIcs), Vol. 145. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 44:1\u201344:18."},{"key":"e_1_3_2_5_2","first-page":"910","volume-title":"Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Batu Tugkan","year":"2004","unstructured":"Tugkan Batu, Sampath Kannan, Sanjeev Khanna, and Andrew McGregor. 2004. Reconstructing strings from random traces. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms. 910\u2013918."},{"issue":"4","key":"e_1_3_2_6_2","first-page":"1323","article-title":"Littlewood-type polynomials on subarcs of the unit circle","volume":"46","author":"Borwein Peter","year":"1997","unstructured":"Peter Borwein and Tam\u00e1s Erd\u00e9lyi. 1997. Littlewood-type polynomials on subarcs of the unit circle. Indiana Univ. Math. J. 46, 4 (1997), 1323\u20131346.","journal-title":"Indiana Univ. Math. J."},{"issue":"79","key":"e_1_3_2_7_2","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1112\/S0024611599011831","article-title":"Littlewood-type problems on \\([0,1]\\)","volume":"3","author":"Borwein Peter","year":"1999","unstructured":"Peter Borwein, Tam\u00e1s Erd\u00e9lyi, and G\u00e9za K\u00f3s. 1999. Littlewood-type problems on \\([0,1]\\) . Proc. London Math. Societ. 3, 79 (1999), 22\u201346.","journal-title":"Proc. London Math. Societ."},{"issue":"2","key":"e_1_3_2_8_2","first-page":"627","article-title":"New lower bounds for trace reconstruction","volume":"57","author":"Chase Zachary","year":"2021","unstructured":"Zachary Chase. 2021. New lower bounds for trace reconstruction. Ann. Inst. H. Poincar\u00e9 57, 2 (2021), 627\u2013643.","journal-title":"Ann. Inst. H. Poincar\u00e9"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451118"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055450"},{"issue":"2","key":"e_1_3_2_11_2","first-page":"851","article-title":"Optimal mean-based algorithms for trace reconstruction","volume":"29","author":"De Anindya","year":"2019","unstructured":"Anindya De, Ryan O\u2019Donnell, and Rocco A. Servedio. 2019. Optimal mean-based algorithms for trace reconstruction. Ann. Appl. Probab. 29, 2 (2019), 851\u2013874.","journal-title":"Ann. Appl. Probab."},{"key":"e_1_3_2_12_2","first-page":"54","volume-title":"Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics.","author":"Hartung Lisa","year":"2018","unstructured":"Lisa Hartung, Nina Holden, and Yuval Peres. 2018. Trace reconstruction with varying deletion probabilities. In Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics.54\u201361."},{"issue":"2","key":"e_1_3_2_13_2","first-page":"503","article-title":"Lower bounds for trace reconstruction","volume":"30","author":"Holden Nina","year":"2020","unstructured":"Nina Holden and Russell Lyons. 2020. Lower bounds for trace reconstruction. Ann. Appl. Probab. 30, 2 (2020), 503\u2013525.","journal-title":"Ann. Appl. Probab."},{"key":"e_1_3_2_14_2","first-page":"1799","volume-title":"Proceedings of the Conference on Learning Theory (Proceedings of Machine Learning Research)","volume":"75","author":"Holden Nina","year":"2018","unstructured":"Nina Holden, Robin Pemantle, and Yuval Peres. 2018. Subpolynomial trace reconstruction for random strings and arbitrary deletion probability. In Proceedings of the Conference on Learning Theory (Proceedings of Machine Learning Research), Vol. 75. PMLR, 1799\u20131840."},{"key":"e_1_3_2_15_2","article-title":"Subpolynomial trace reconstruction for random strings and arbitrary deletion probability","volume":"1801","author":"Holden Nina","year":"2020","unstructured":"Nina Holden, Robin Pemantle, Yuval Peres, and Alex Zhai. 2020. Subpolynomial trace reconstruction for random strings and arbitrary deletion probability. CoRR abs\/1801.04783 (2020).","journal-title":"CoRR"},{"key":"e_1_3_2_16_2","first-page":"389","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Holenstein Thomas","year":"2008","unstructured":"Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder. 2008. Trace reconstruction with constant deletion probability and related results. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 389\u2013398."},{"key":"e_1_3_2_17_2","first-page":"56","article-title":"Reconstruction of a word from its fragments","volume":"4","author":"Kalashnik V. V.","year":"1973","unstructured":"V. V. Kalashnik. 1973. Reconstruction of a word from its fragments. Computat. Math. Comput. Sci. (Vychislitel\u2019naya matematika i vychislitel\u2019naya tekhnika), Kharkov 4 (1973), 56\u201357.","journal-title":"Computat. Math. Comput. Sci. (Vychislitel\u2019naya matematika i vychislitel\u2019naya tekhnika), Kharkov"},{"key":"e_1_3_2_18_2","first-page":"297","volume-title":"Proceedings of the IEEE International Symposium on Information Theory","author":"Kannan Sampath","year":"2005","unstructured":"Sampath Kannan and Andrew McGregor. 2005. More on reconstructing strings from random traces: Insertions and deletions. In Proceedings of the IEEE International Symposium on Information Theory. 297\u2013301."},{"key":"e_1_3_2_19_2","first-page":"68:1\u201368:25","volume-title":"Proceedings of the 27th Annual European Symposium on Algorithms (LIPIcs)","volume":"144","author":"Krishnamurthy Akshay","year":"2019","unstructured":"Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. 2019. Trace Reconstruction: Generalized and parameterized. In Proceedings of the 27th Annual European Symposium on Algorithms (LIPIcs), Vol. 144. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 68:1\u201368:25."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.904499"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3081"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_57"},{"key":"e_1_3_2_23_2","first-page":"1259","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms","author":"Narayanan Shyam","year":"2021","unstructured":"Shyam Narayanan. 2021. Improved algorithms for population recovery from the deletion channel. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1259\u20131278."},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"1042","DOI":"10.1145\/3055399.3055494","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing","author":"Nazarov Fedor","year":"2017","unstructured":"Fedor Nazarov and Yuval Peres. 2017. Trace reconstruction with \\(\\exp (O(n^{1\/3}))\\) samples. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. 1042\u20131046."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_2_26_2","first-page":"228","volume-title":"Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science","author":"Peres Yuval","year":"2017","unstructured":"Yuval Peres and Alex Zhai. 2017. Average-case reconstruction for the deletion channel: Subpolynomially many traces suffice. In Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science. 228\u2013239. https:\/\/arxiv.org\/abs\/1708.00854."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_3_2_28_2","series-title":"(Graduate Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/097","volume-title":"Complex Made Simple","author":"Ullrich David C.","year":"2008","unstructured":"David C. Ullrich. 2008. Complex Made Simple. (Graduate Studies in Mathematics, Vol. 97.) American Mathematical Society."},{"key":"e_1_3_2_29_2","first-page":"399","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Viswanathan Krishnamurthy","year":"2008","unstructured":"Krishnamurthy Viswanathan and Ram Swaminathan. 2008. Improved string reconstruction over insertion-deletion channels. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms. 399\u2013408."},{"key":"e_1_3_2_30_2","unstructured":"Wikipedia contributors. Hadamard three-circle theorem. Wikipedia The Free Encyclopedia. Retrieved 12 April 2021 from https:\/\/en.wikipedia.org\/wiki\/Hadamard_three-circle_theorem."},{"key":"e_1_3_2_31_2","unstructured":"Wikipedia contributors. Jensen\u2019s formula. Wikipedia The Free Encyclopedia. Retrieved 8 July 2021 from https:\/\/en.wikipedia.org\/wiki\/Jensen%27s_formula."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3560819","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,26]],"date-time":"2025-07-26T09:28:19Z","timestamp":1753522099000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3560819"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,26]]},"references-count":30,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,7,31]]}},"alternative-id":["10.1145\/3560819"],"URL":"https:\/\/doi.org\/10.1145\/3560819","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,7,26]]},"assertion":[{"value":"2021-03-24","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-19","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}