{"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":1776956046610,"version":"3.51.4"},"reference-count":45,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"4","license":[{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,4,1]],"date-time":"2025-04-01T00:00:00Z","timestamp":1743465600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62472008"],"award-info":[{"award-number":["62472008"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["CCF-1910411"],"award-info":[{"award-number":["CCF-1910411"]}]},{"name":"NSF","award":["CCF-2228814"],"award-info":[{"award-number":["CCF-2228814"]}]},{"name":"NSF CAREER Award","award":["CCF-1845349"],"award-info":[{"award-number":["CCF-1845349"]}]},{"name":"NSF","award":["CCF-2127575"],"award-info":[{"award-number":["CCF-2127575"]}]},{"name":"Simons Investigator Award and in part by NSF Award","award":["CCF 2152413"],"award-info":[{"award-number":["CCF 2152413"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2025,4]]},"DOI":"10.1109\/tit.2025.3541375","type":"journal-article","created":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T18:36:21Z","timestamp":1739471781000},"page":"2591-2603","source":"Crossref","is-referenced-by-count":5,"title":["On <i>k<\/i>-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction"],"prefix":"10.1109","volume":"71","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8972-1749","authenticated-orcid":false,"given":"Kuan","family":"Cheng","sequence":"first","affiliation":[{"name":"School of Computer Science, Peking University, Haidian, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9673-4313","authenticated-orcid":false,"given":"Elena","family":"Grigorescu","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9408-2451","authenticated-orcid":false,"given":"Xin","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Johns Hopkins University, Baltimore, MD, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3718-6489","authenticated-orcid":false,"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[{"name":"School of Engineering and Applied Sciences, Harvard University, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1927-6085","authenticated-orcid":false,"given":"Minshen","family":"Zhu","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Purdue University, West Lafayette, IN, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref1","first-page":"910","article-title":"Reconstructing strings from random traces","volume-title":"Proc. ACM-SIAM Symp. Discrete Algorithms (SODA)","author":"Batu"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451118"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055494"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1214\/18-AAP1394"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1214\/19-AAP1506"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1214\/20-AIHP1089"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2005.1523342"},{"key":"ref8","first-page":"399","article-title":"Improved string reconstruction over insertion-deletion channels","volume-title":"Proc. 19th Annu. ACM-SIAM Symp. Discrete Algorithms","author":"Viswanathan"},{"key":"ref9","first-page":"389","article-title":"Trace reconstruction with constant deletion probability and related results","volume-title":"Proc. ACM-SIAM Symp. Discrete Algorithms (SODA)","author":"Holenstein"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_57"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.29"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006740"},{"key":"ref13","first-page":"1799","article-title":"Subpolynomial trace reconstruction for random strings and arbitrary deletion probability","volume-title":"Proc. Conf. Learn. Theory (COLT)","author":"Holden"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975062.6"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2935973"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2996377"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3066010"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00052"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.5"},{"key":"ref20","article-title":"Approximate trace reconstruction of random strings from a constant number of traces","author":"Chase","year":"2021","journal-title":"arXiv:2107.06454"},{"key":"ref21","first-page":"18:1","article-title":"Circular trace reconstruction","volume-title":"Proc. 12th Innov. Theor. Comput. Sci. Conf. (ITCS)","author":"Narayanan"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9518244"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1109\/tit.2022.3168624"},{"key":"ref24","article-title":"Average-case to (shifted) worst-case reduction for the trace reconstruction problem","volume-title":"Proc. 50th Int. Colloq. Automata, Lang., Program. (ICALP)","author":"Rubinstein"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-017-05188-1"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1109\/tit.2024.3418377"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9518161"},{"issue":"6","key":"ref28","first-page":"1323","article-title":"Littlewood-type problems on subarcs of the unit circle","volume":"46","author":"Borwein","year":"1997","journal-title":"Indiana Univ. Math. J."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0021-9045(80)90069-6"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/13623"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2000.3081"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/18.904499"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00050"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.1997.2732"},{"issue":"1","key":"ref35","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/S0012-365X(96)00153-7","article-title":"Reconstructing sequences","volume":"175","author":"Scott","year":"1997","journal-title":"Discrete Math."},{"issue":"2","key":"ref36","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0097-3165(03)00103-1","article-title":"Reconstruction from subsequences","volume":"103","author":"Dud\u00edk","year":"2003","journal-title":"J. Combinat. Theory, Ser. A"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT45174.2021.9517926"},{"key":"ref38","article-title":"Near-optimal average-case approximate trace reconstruction from few traces","author":"Chen","year":"2021","journal-title":"arXiv:2107.11530"},{"key":"ref39","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)","author":"Chakraborty"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.3033513"},{"key":"ref41","article-title":"Trace reconstruction from local statistical queries","volume":"317","author":"Chen","year":"2024","journal-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)"},{"issue":"6","key":"ref42","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1145\/293347.293351","article-title":"Efficient noise-tolerant learning from statistical queries","volume":"45","author":"Kearns","year":"1998","journal-title":"J. ACM"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1112\/S0024611599011831"},{"key":"ref44","volume":"103","author":"Lang","year":"2013","journal-title":"Complex Analysis"},{"key":"ref45","volume-title":"Approximation Theory and Approximation Practice","author":"Trefethen","year":"2012"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/18\/10935829\/10884609.pdf?arnumber=10884609","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T03:33:23Z","timestamp":1743132803000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10884609\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4]]},"references-count":45,"journal-issue":{"issue":"4"},"URL":"https:\/\/doi.org\/10.1109\/tit.2025.3541375","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4]]}}}