{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:32:20Z","timestamp":1750221140442,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1527110, CCF-1618280 and CCF-175080"],"award-info":[{"award-number":["CCF-1527110, CCF-1618280 and CCF-175080"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188940","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"841-854","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":22,"title":["Synchronization strings: explicit constructions, local decoding, and applications"],"prefix":"10.1145","author":[{"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, USA"}]},{"given":"Amirbehshad","family":"Shahrasbi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796292"},{"key":"e_1_3_2_2_2_1","unstructured":"Arturs Backurs and Piotr Indyk. 2015.  Arturs Backurs and Piotr Indyk. 2015."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_2_4_1","unstructured":"J Beck. 1984.  J Beck. 1984."},{"volume-title":"Finite and Infinite Sets","author":"An","key":"e_1_3_2_2_5_1"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.22"},{"key":"e_1_3_2_2_7_1","unstructured":"Zvika Brakerski and Moni Naor. 2013.  Zvika Brakerski and Moni Naor. 2013."},{"volume-title":"Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 443\u2013456","author":"Fast","key":"e_1_3_2_2_8_1"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2017.2734881"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2353994"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/100799642"},{"key":"e_1_3_2_2_12_1","unstructured":"Kuan Cheng Xin Li and Ke Wu. 2017.  Kuan Cheng Xin Li and Ke Wu. 2017."},{"volume-title":"Efficient and Fast Deterministic Constructions over Small Alphabets. arXiv preprint arXiv:1710.07356","year":"2017","author":"Strings Synchronization","key":"e_1_3_2_2_13_1"},{"key":"e_1_3_2_2_14_1","unstructured":"Matthew Franklin Ran Gelles Rafail Ostrovsky and Leonard J Schulman. 2015.  Matthew Franklin Ran Gelles Rafail Ostrovsky and Leonard J Schulman. 2015."},{"volume-title":"IEEE Transactions on Information Theory 61, 1","year":"2015","author":"Optimal","key":"e_1_3_2_2_15_1"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2294186"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.49"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1963.1088781"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875548"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.855587"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541373"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132518"},{"volume-title":"Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM). 867\u2013880","year":"2015","author":"Guruswami Venkatesan","key":"e_1_3_2_2_23_1"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.32"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055498"},{"volume-title":"Synchronization Strings: Explicit Constructions, Local Decoding, and Applications. arXiv preprint arXiv:1710.09795","year":"2017","author":"Haeupler Bernhard","key":"e_1_3_2_2_26_1"},{"volume-title":"Proceedings of the International Conference on Automata, Languages, and Programming (ICALP).","year":"2018","author":"Haeupler Bernhard","key":"e_1_3_2_2_27_1"},{"volume-title":"Proceedings of the International Conference on Automata, Languages, and Programming (ICALP).","year":"2018","author":"Haeupler Bernhard","key":"e_1_3_2_2_28_1"},{"volume-title":"Proceedings of the Annual Symposium on Foundations of Computer Science (FOCS).","year":"2017","author":"Hemenway Brett","key":"e_1_3_2_2_29_1"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488699"},{"volume-title":"Binary codes capable of correcting deletions, insertions, and reversals. Doklady Akademii Nauk SSSR 163 4","year":"1965","author":"Levenshtein Vladimir","key":"e_1_3_2_2_31_1"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/SURV.2010.020110.00079"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267778"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556671"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.796406"},{"key":"e_1_3_2_2_36_1","first-page":"79","article-title":"Optimal Interactive Coding for Insertions, Deletions, and Substitutions","volume":"24","author":"Sherstov Alexander A","year":"2017","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556667"},{"volume-title":"On single-deletion-correcting codes. Codes and Designs","year":"2002","author":"Sloane Neil JA","key":"e_1_3_2_2_38_1"},{"key":"e_1_3_2_2_39_1","unstructured":"Daniel Alan Spielman. 1995.  Daniel Alan Spielman. 1995."}],"event":{"name":"STOC '18: Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Los Angeles CA USA","acronym":"STOC '18"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188940","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188940","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T01:08:07Z","timestamp":1750208887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":39,"alternative-id":["10.1145\/3188745.3188940","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188940","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}