{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:04:38Z","timestamp":1750309478027,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":31,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["DMS-2103154, DMS-2203067"],"award-info":[{"award-number":["DMS-2103154, DMS-2203067"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585104","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1145-1158","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating Binary Longest Common Subsequence in Almost-Linear Time"],"prefix":"10.1145","author":[{"given":"Xiaoyu","family":"He","sequence":"first","affiliation":[{"name":"Princeton University, USA"}]},{"given":"Ray","family":"Li","sequence":"additional","affiliation":[{"name":"University of California at Berkeley, Berkeley, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.11"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.35"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"volume-title":"Longest Common Subsequence Over Constant-Sized Alphabets: Beating the Naive Approximation Ratio. Master\u2019s thesis","author":"Akmal Shyan","key":"e_1_3_2_1_6_1","unstructured":"Shyan Akmal . 2021. Longest Common Subsequence Over Constant-Sized Alphabets: Beating the Naive Approximation Ratio. Master\u2019s thesis . Massachusetts Institute of Technology . Shyan Akmal. 2021. Longest Common Subsequence Over Constant-Sized Alphabets: Beating the Naive Approximation Ratio. Master\u2019s thesis. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.13"},{"key":"e_1_3_2_1_8_1","unstructured":"Alexandr Andoni. 2018. Simpler constant-factor approximation to edit distance problems. http:\/\/www.cs.columbia.edu\/~andoni\/papers\/edit\/ \t\t\t\t  Alexandr Andoni. 2018. Simpler constant-factor approximation to edit distance problems. http:\/\/www.cs.columbia.edu\/~andoni\/papers\/edit\/"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00096"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00073"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767182"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.14"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384282"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.39"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2621044"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422823"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.1"},{"volume-title":"Selected combinatorial research problems. Computer Science Department","author":"Chv\u00e1tal Va\u0161ek","key":"e_1_3_2_1_21_1","unstructured":"Va\u0161ek Chv\u00e1tal , David A Klarner , and Donald Ervin Knuth . 1972. Selected combinatorial research problems. Computer Science Department , Stanford University . Va\u0161ek Chv\u00e1tal, David A Klarner, and Donald Ervin Knuth. 1972. Selected combinatorial research problems. Computer Science Department, Stanford University."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384300"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00076"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.72"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384307"},{"key":"e_1_3_2_1_26_1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"10","author":"Levenshtein Vladmir I.","year":"1966","unstructured":"Vladmir I. Levenshtein . 1966 . Binary codes capable of correcting deletions, insertions and reversals . Soviet Physics Dokl. (English Translation) , 10 , 8 (1966), 707 \u2013 710 . Vladmir I. Levenshtein. 1966. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Dokl. (English Translation), 10, 8 (1966), 707\u2013710.","journal-title":"Soviet Physics Dokl. (English Translation)"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_3_2_1_28_1","volume-title":"Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time. CoRR, abs\/2112.08454","author":"Nosatzki Negev Shekel","year":"2021","unstructured":"Negev Shekel Nosatzki . 2021. Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time. CoRR, abs\/2112.08454 ( 2021 ), arXiv:2112.08454. arxiv:2112.08454 Negev Shekel Nosatzki. 2021. Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time. CoRR, abs\/2112.08454 (2021), arXiv:2112.08454. arxiv:2112.08454"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00071"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.98"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1053954"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585104","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585104","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585104"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":31,"alternative-id":["10.1145\/3564246.3585104","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585104","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}