{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T04:38:59Z","timestamp":1773376739739,"version":"3.50.1"},"reference-count":19,"publisher":"IEEE","license":[{"start":{"date-parts":[[2024,7,7]],"date-time":"2024-07-07T00:00:00Z","timestamp":1720310400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2024,7,7]],"date-time":"2024-07-07T00:00:00Z","timestamp":1720310400000},"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":["1934846"],"award-info":[{"award-number":["1934846"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,7,7]]},"DOI":"10.1109\/isit57864.2024.10619491","type":"proceedings-article","created":{"date-parts":[[2024,8,19]],"date-time":"2024-08-19T13:25:01Z","timestamp":1724073901000},"page":"3462-3467","source":"Crossref","is-referenced-by-count":0,"title":["Graph Reconstruction from Noisy Random Subgraphs"],"prefix":"10.1109","author":[{"given":"Andrew","family":"McGregor","sequence":"first","affiliation":[{"name":"University of Massachusetts Amherst,Manning College of Information and Computer Sciences,Amherst,MA,USA"}]},{"given":"Rik","family":"Sengupta","sequence":"additional","affiliation":[{"name":"IBM Research,MIT-IBM Watson AI Lab,Cambridge,MA,USA"}]}],"member":"263","reference":[{"key":"ref1","first-page":"96: 1","article-title":"Graph Reconstruction from Random Subgraphs","volume-title":"49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), ser. Leibniz International Proceedings in Informatics (LIPIcs)","volume":"229","author":"McGregor"},{"key":"ref2","article-title":"Reconstructing strings from random traces","volume-title":"Symposium on Discrete Algorithms","author":"Batu","year":"2004"},{"key":"ref3","article-title":"Improved string reconstruction over insertion-deletion channels","volume-title":"Symposium on Discrete Algorithms","author":"Viswanathan","year":"2008"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44777-2_57"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.4171\/msl\/16"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055494"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.29"},{"issue":"2","key":"ref8","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1214\/19-AAP1506","article-title":"Lower bounds for trace reconstruction","volume":"30","author":"Holden","year":"2020","journal-title":"The Annals of Applied Probability"},{"key":"ref9","article-title":"Trace reconstruction with constant deletion probability and related results","volume-title":"Symposium on Discrete Algorithms","author":"Holenstein","year":"2008"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/tit.2021.3066010"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055450"},{"key":"ref12","first-page":"18:1","article-title":"Circular Trace Reconstruction","volume-title":"12th Innovations in Theoretical Computer Science Conference (ITCS 2021), ser. Leibniz International Proceedings in Informatics (LIPIcs)","volume":"185","author":"Narayanan"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975062.6"},{"key":"ref14","first-page":"961","article-title":"Reconstructing trees from traces","volume-title":"Proceedings of the Thirty-Second Conference on Learning Theory, ser. Proceedings of Machine Learning Research","volume":"99","author":"Davies"},{"key":"ref15","article-title":"Tree trace reconstruction using subtraces","volume":"abs\/2102.01541","author":"Brailovskaya","year":"2021","journal-title":"CoRR"},{"key":"ref16","article-title":"Reconstructing arbitrary trees from traces in the tree edit distance model","volume":"abs\/2102.03173","author":"Maranzatto","year":"2021","journal-title":"CoRR"},{"key":"ref17","doi-asserted-by":"crossref","first-page":"961","DOI":"10.2140\/pjm.1957.7.961","article-title":"A congruence theorem for trees","volume":"7","author":"Kelly","year":"1957","journal-title":"Pacific Journal of Mathematics"},{"key":"ref18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/jgt.3190140102","article-title":"Almost every graph has reconstruction number three","volume":"14","author":"Bollob\u00e1s","year":"1990","journal-title":"J. Graph Theory"},{"key":"ref19","article-title":"Graph reconstruction from noisy random subgraphs","volume":"abs\/2405.04261","author":"McGregor","year":"2024","journal-title":"CoRR"}],"event":{"name":"2024 IEEE International Symposium on Information Theory (ISIT)","location":"Athens, Greece","start":{"date-parts":[[2024,7,7]]},"end":{"date-parts":[[2024,7,12]]}},"container-title":["2024 IEEE International Symposium on Information Theory (ISIT)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/10619013\/10619074\/10619491.pdf?arnumber=10619491","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T20:28:02Z","timestamp":1773347282000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/10619491\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,7]]},"references-count":19,"URL":"https:\/\/doi.org\/10.1109\/isit57864.2024.10619491","relation":{},"subject":[],"published":{"date-parts":[[2024,7,7]]}}}