{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T14:54:06Z","timestamp":1776956046584,"version":"3.51.4"},"reference-count":47,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"10","license":[{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"am","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T00:00:00Z","timestamp":1664582400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1910659"],"award-info":[{"award-number":["CCF-1910659"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1910411"],"award-info":[{"award-number":["CCF-1910411"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Simons Investigator Award"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF 1715187"],"award-info":[{"award-number":["CCF 1715187"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1109\/tit.2022.3168624","type":"journal-article","created":{"date-parts":[[2022,4,18]],"date-time":"2022-04-18T20:20:07Z","timestamp":1650313207000},"page":"6790-6801","source":"Crossref","is-referenced-by-count":6,"title":["Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance"],"prefix":"10.1109","volume":"68","author":[{"given":"Elena","family":"Grigorescu","sequence":"first","affiliation":[{"name":"Computer Science Department, Purdue University, West Lafayette, IN, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3718-6489","authenticated-orcid":false,"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"Harvard John A. Paulson School of Engineering and Applied Sciences, Harvard University, Boston, MA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1927-6085","authenticated-orcid":false,"given":"Minshen","family":"Zhu","sequence":"additional","affiliation":[{"name":"Computer Science Department, Purdue University, West Lafayette, IN, USA"}]}],"member":"263","reference":[{"key":"ref1","first-page":"910","article-title":"Reconstructing strings from random traces","volume-title":"Proc. 15th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA)","author":"Batu"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2005.1523342"},{"key":"ref3","first-page":"399","article-title":"Improved string reconstruction over insertion-deletion channels","volume-title":"Proc. 19th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA)","author":"Viswanathan"},{"key":"ref4","first-page":"389","article-title":"Trace reconstruction with constant deletion probability and related results","volume-title":"Proc. 19th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA)","author":"Holenstein"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_57"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.29"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055494"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1214\/18-AAP1394"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006740"},{"key":"ref10","first-page":"1799","article-title":"Subpolynomial trace reconstruction for random strings and arbitrary deletion probability","volume-title":"Proc. Conf. Learn. Theory (COLT)","volume":"75","author":"Holden"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1214\/19-AAP1506"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975062.6"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2935973"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2996377"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3066010"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00052"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.5"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451118"},{"key":"ref19","first-page":"18:1","article-title":"Circular trace reconstruction","volume-title":"Proc. 12th Innov. Theor. Comput. Sci. Conf. (ITCS)","volume":"185","author":"Narayanan"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1214\/20-AIHP1089"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1512\/iumj.1997.46.1435"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2732"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00153-7"},{"issue":"225","key":"ref24","first-page":"1851","article-title":"M\u00e9moire sur quelques relations entre les puissances des nombres","volume":"33","author":"Prouhet","year":"1851","journal-title":"CR Acad. Sci. Paris"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.5962\/t.174912"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1959.11989269"},{"issue":"1","key":"ref27","first-page":"29","article-title":"On the product n $k=1$\n (1-zak), acad","volume":"13","author":"Erdos","year":"1959","journal-title":"Serbe Sci. Publication Inst. Math."},{"issue":"1","key":"ref28","first-page":"3","article-title":"The Prouhet-Tarry-Escott problem revisited","volume":"40","author":"Borwein","year":"1994","journal-title":"Enseign. Math"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/os-6.1.261"},{"key":"ref30","volume-title":"Introduction to Number Theory","author":"Hua","year":"1982"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/16M110349X"},{"key":"ref32","volume-title":"La G\u00e9om\u00e9trie","author":"Descartes","year":"1886"},{"key":"ref33","article-title":"Limitations of mean-based algorithms for trace reconstruction at small distance","author":"Grigorescu","year":"2020","journal-title":"arXiv:2011.13737"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9518244"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6292-1"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.4064\/aa8129-11-2015"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-60622-0_9"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3081"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1109\/18.904499"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9518161"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00050"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9517926"},{"key":"ref43","article-title":"Near-optimal average-case approximate trace reconstruction from few traces","author":"Chen","year":"2021","journal-title":"arXiv:2107.11530"},{"key":"ref44","article-title":"Approximate trace reconstruction of random strings from a constant number of traces","author":"Chase","year":"2021","journal-title":"arXiv:2107.06454"},{"key":"ref45","first-page":"11:1","article-title":"Approximate trace reconstruction via median string (in average-case)","volume-title":"Proc. 41st IARCS Annu. Conf. Found. Softw. Technol. Theor. Comput. Sci. (FSTTCS)","volume":"213","author":"Chakraborty"},{"key":"ref46","volume-title":"Complex Analysis","volume":"103","author":"Lang","year":"2013"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611599011831"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"https:\/\/ieeexplore.ieee.org\/ielam\/18\/9893495\/9759421-aam.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/9893495\/09759421.pdf?arnumber=9759421","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,22]],"date-time":"2024-01-22T20:45:29Z","timestamp":1705956329000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9759421\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":47,"journal-issue":{"issue":"10"},"URL":"https:\/\/doi.org\/10.1109\/tit.2022.3168624","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10]]}}}