{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:04:44Z","timestamp":1781028284539,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":74,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"NSF CAREER Award","award":["CCF-2337901"],"award-info":[{"award-number":["CCF-2337901"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800789","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"744-754","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1224-9730","authenticated-orcid":false,"given":"Xiao","family":"Mao","sequence":"first","affiliation":[{"name":"Stanford University, STANFORD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6900-8612","authenticated-orcid":false,"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[{"name":"Stanford University, STANFORD, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"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.4230\/LIPIcs.ICALP.2018.8"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649696"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.35"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_4"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2021.13"},{"key":"e_1_3_2_1_9_1","unstructured":"Alexandr Andoni. 2020. Simple Constant-Factor Approximation to Edit Distance. https:\/\/www.cs.columbia.edu\/ andoni\/papers\/edit\/simple.pdf"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644196"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/080716530"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2344422.2344434"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.8"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00096"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/090767182"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1053128"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.14"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780590"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109644"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3456807"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316388"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2021.3076534"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.99"},{"key":"e_1_3_2_1_25_1","volume-title":"A Simple Sublinear Algorithm for Gap Edit Distance. CoRR, abs\/2007.14368","author":"Brakensiek Joshua","year":"2020","unstructured":"Joshua Brakensiek, Moses Charikar, and Aviad Rubinstein. 2020. A Simple Sublinear Algorithm for Gap Edit Distance. CoRR, abs\/2007.14368 (2020), arXiv:2007.14368. arxiv:2007.14368"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384282"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.76"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.117"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519990"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519990"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.32"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3568398"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00135"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3422823"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897577"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.48"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.34"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.1"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.54"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the 57th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2025","author":"Cheng Siu-Wing","year":"2025","unstructured":"Siu-Wing Cheng, Haoqiang Huang, and Shuo Zhang. 2025. Constant Approximation of Fr\u00e9chet Distance in Strongly Subquadratic Time. In Proceedings of the 57th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2025, Prague, Czech Republic, June 23-27, 2025."},{"key":"e_1_3_2_1_42_1","volume-title":"Knuth","author":"Chv\u00e1tal V\u00e1clav","year":"1972","unstructured":"V\u00e1clav Chv\u00e1tal, David A. Klarner, and Donald E. Knuth. 1972. Selected combinatorial research problems.. Computer Science Department, Stanford University. https:\/\/pdfs.semanticscholar.org\/e832\/afd53b720bbb2c3dfff89f5005d5c395719f.pdf"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2493252.2493257"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718179"},{"key":"e_1_3_2_1_45_1","unstructured":"Pawe\u0142 Gawrychowski Shay Mozes and Oren Weimann. 2019. Minimum Cut in O(m log ^ 2 n) Time. arXiv preprint arXiv:1911.01145 Best ICALP Paper"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00070"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00070"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384300"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718168"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.10.040"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316371"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.72"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.100"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585104"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2021.45"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649605"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00090"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00112"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384307"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch188"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649783"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/060660126"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.71"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","unstructured":"Kasper Green Larsen and Ryan Williams. 2017. Faster Online Matrix-Vector Multiplication. 2182\u20132189. arxiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611974782.142. https:\/\/doi.org\/10.1137\/1.9781611974782.142 10.1137\/1.9781611974782.142","DOI":"10.1137\/1.9781611974782.142"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_3_2_1_67_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"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284320.1284322"},{"key":"e_1_3_2_1_69_1","unstructured":"Binghui Peng. 2025. High dimensional online calibration in polynomial time. arxiv:2504.09096. arxiv:2504.09096"},{"key":"e_1_3_2_1_70_1","unstructured":"Aviad Rubinstein. 2018. Approximating Edit Distance. https:\/\/theorydish.blog\/2018\/07\/20\/approximating-edit-distance\/"},{"key":"e_1_3_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1316500"},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.98"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2022.115"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1024524"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800789","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:56:38Z","timestamp":1781027798000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800789"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":74,"alternative-id":["10.1145\/3798129.3800789","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800789","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}