{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:47Z","timestamp":1781077727518,"version":"3.54.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Unions Horizon 2020 research and innovation programme","award":["850979"],"award-info":[{"award-number":["850979"]}]},{"DOI":"10.13039\/501100020975","name":"Basic Algorithms Research Copenhagen","doi-asserted-by":"crossref","award":["16582"],"award-info":[{"award-number":["16582"]}],"id":[{"id":"10.13039\/501100020975","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>\n            We consider the classic problem of computing the\n            <jats:bold>Longest Common Subsequence (LCS)<\/jats:bold>\n            of two strings of length\n            <jats:italic>n<\/jats:italic>\n            . The 40-year-old quadratic-time dynamic programming algorithm has recently been shown to be near-optimal by Abboud, Backurs, and Vassilevska Williams [FOCS\u201915] and Bringmann and K\u00fcnnemann [FOCS\u201915] assuming the Strong Exponential Time Hypothesis. This has led the community to look for subquadratic\n            <jats:italic>approximation<\/jats:italic>\n            algorithms for the problem.\n          <\/jats:p>\n          <jats:p>\n            Yet, unlike the edit distance problem for which a constant-factor approximation in almost-linear time is known, very little progress has been made on LCS, making it a notoriously difficult problem also in the realm of approximation. For the general setting, only a naive\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u025b<\/jats:sup>\n            \/2-approximation algorithm with running time\n            <jats:italic>O\u0160<\/jats:italic>\n            (\n            <jats:italic>\n              n\n              <jats:sup>2-\u025b<\/jats:sup>\n            <\/jats:italic>\n            has been known, for any constant 0 &lt; \u025b \u2264 1. Recently, a breakthrough result by Hajiaghayi, Seddighin, Seddighin, and Sun [SODA\u201919] provided a linear-time algorithm that yields a\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.497956<\/jats:sup>\n            -approximation in expectation; improving upon the naive\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\sqrt {n})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximation for the first time.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we provide an algorithm that in time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sub>2-\u025b<\/jats:sub>\n            ) computes an\n            <jats:italic>O\u0160<\/jats:italic>\n            (\n            <jats:italic>\n              n\n              <jats:sup>2\u025b\/5<\/jats:sup>\n            <\/jats:italic>\n            -approximation with high probability, for any 0 &lt; \u025b \u2264 1. Our result (1) gives an\n            <jats:italic>O\u0160<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>0.4<\/jats:sup>\n            -approximation in linear time, improving upon the bound of Hajiaghayi, Seddighin, Seddighin, and Sun, (2) provides an algorithm whose approximation scales with any subquadratic running time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2-\u025b<\/jats:sup>\n            ), improving upon the naive bound of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u025b\/2<\/jats:sup>\n            ) for any \u025b, and (3) instead of only in expectation, succeeds with high probability.\n          <\/jats:p>","DOI":"10.1145\/3568398","type":"journal-article","created":{"date-parts":[[2022,10,26]],"date-time":"2022-10-26T14:16:17Z","timestamp":1666793777000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Linear-Time\n            <i>n<\/i>\n            <sup>0.4<\/sup>\n            -Approximation for Longest Common Subsequence"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1356-5177","authenticated-orcid":false,"given":"Karl","family":"Bringmann","sequence":"first","affiliation":[{"name":"Saarland University and Max-Planck-Institute for Informatics, Saarland Informatics Campus, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0779-8962","authenticated-orcid":false,"given":"Vincent","family":"Cohen-Addad","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, UPMC Univ Paris 06, CNRS, LIP6, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2232-4279","authenticated-orcid":false,"given":"Debarati","family":"Das","sequence":"additional","affiliation":[{"name":"Basic Algorithm\u00a0Research Copenhagen (BARC), University of Copenhagen, Copenhagen, Denmark"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,2,20]]},"reference":[{"key":"e_1_3_4_2_2","series-title":"LIPIcs","first-page":"11:1\u201311:26","volume-title":"ITCS","author":"Abboud Amir","year":"2017","unstructured":"Amir Abboud and Arturs Backurs. 2017. Towards hardness of approximation for polynomial time problems. In ITCS(LIPIcs, Vol. 67). 11:1\u201311:26."},{"key":"e_1_3_4_3_2","first-page":"59","volume-title":"FOCS","author":"Abboud Amir","year":"2015","unstructured":"Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. 2015. Tight hardness results for LCS and other sequence similarity measures. In FOCS. IEEE, 59\u201378."},{"key":"e_1_3_4_4_2","series-title":"LIPIcs","first-page":"8:1\u20138:18","volume-title":"ICALP","author":"Abboud Amir","year":"2018","unstructured":"Amir Abboud and Karl Bringmann. 2018. Tighter connections between Formula-SAT and shaving logs. In ICALP(LIPIcs, Vol. 107). 8:1\u20138:18."},{"key":"e_1_3_4_5_2","first-page":"375","volume-title":"STOC","author":"Abboud Amir","year":"2016","unstructured":"Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. 2016. Simulating branching programs with edit distance and friends: Or: A polylog shaved is a lower bound made. In STOC. ACM, 375\u2013388."},{"key":"e_1_3_4_6_2","series-title":"LIPIcs","first-page":"35:1\u201335:14","volume-title":"ITCS","author":"Abboud Amir","year":"2018","unstructured":"Amir Abboud and Aviad Rubinstein. 2018. Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. In ITCS(LIPIcs, Vol. 94). 35:1\u201335:14."},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321922"},{"key":"e_1_3_4_8_2","series-title":"LIPIcs","first-page":"13:1\u201313:18","volume-title":"ICALP","author":"Akmal Shyan","year":"2021","unstructured":"Shyan Akmal and Virginia Vassilevska Williams. 2021. Improved approximation for longest common subsequence over small alphabets. In ICALP(LIPIcs, Vol. 198). 13:1\u201313:18."},{"key":"e_1_3_4_9_2","first-page":"377","volume-title":"FOCS","author":"Andoni Alexandr","year":"2010","unstructured":"Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. 2010. Polylogarithmic approximation for edit distance and the asymmetric query complexity. In FOCS. IEEE, 377\u2013386."},{"key":"e_1_3_4_10_2","first-page":"990","volume-title":"FOCS","author":"Andoni Alexandr","year":"2020","unstructured":"Alexandr Andoni and Negev Shekel Nosatzki. 2020. Edit distance in near-linear time: It\u2019s a constant factor. In FOCS. IEEE, 990\u20131001."},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/090767182"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90044-X"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840365"},{"key":"e_1_3_4_14_2","first-page":"51","volume-title":"STOC","author":"Backurs Arturs","year":"2015","unstructured":"Arturs Backurs and Piotr Indyk. 2015. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In STOC. ACM, 51\u201358."},{"key":"e_1_3_4_15_2","first-page":"550","volume-title":"FOCS","author":"Bar-Yossef Ziv","year":"2004","unstructured":"Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar. 2004. Approximating edit distance efficiently. In FOCS. IEEE, 550\u2013559."},{"key":"e_1_3_4_16_2","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1145\/780542.780590","volume-title":"STOC","author":"Batu Tugkan","year":"2003","unstructured":"Tugkan Batu, Funda Erg\u00fcn, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, and Rahul Sami. 2003. A sublinear algorithm for weakly approximating edit distance. In STOC. ACM, 316\u2013324."},{"key":"e_1_3_4_17_2","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/1109557.1109644","volume-title":"SODA","author":"Batu Tugkan","year":"2006","unstructured":"Tugkan Batu, Funda Erg\u00fcn, and S\u00fcleyman Cenk Sahinalp. 2006. Oblivious string embeddings and edit distance approximations. In SODA. ACM, 792\u2013801."},{"key":"e_1_3_4_18_2","first-page":"39","volume-title":"SPIRE","author":"Bergroth Lasse","year":"2000","unstructured":"Lasse Bergroth, Harri Hakonen, and Timo Raita. 2000. A survey of longest common subsequence algorithms. In SPIRE. IEEE, 39\u201348."},{"key":"e_1_3_4_19_2","first-page":"685","volume-title":"STOC","author":"Brakensiek Joshua","year":"2020","unstructured":"Joshua Brakensiek and Aviad Rubinstein. 2020. Constant-factor approximation of near-linear edit distance in near-linear time. In STOC. ACM, 685\u2013698."},{"key":"e_1_3_4_20_2","series-title":"LNCS","first-page":"267","volume-title":"ICALP","author":"Bringmann Karl","year":"2013","unstructured":"Karl Bringmann and Tobias Friedrich. 2013. Exact and efficient generation of geometric random variates and random graphs. In ICALP(LNCS, Vol. 7965). 267\u2013278."},{"key":"e_1_3_4_21_2","first-page":"79","volume-title":"FOCS","author":"Bringmann Karl","year":"2015","unstructured":"Karl Bringmann and Marvin K\u00fcnnemann. 2015. Quadratic conditional lower bounds for string problems and dynamic time warping. In FOCS. IEEE, 79\u201397."},{"key":"e_1_3_4_22_2","first-page":"1216","volume-title":"SODA","author":"Bringmann Karl","year":"2018","unstructured":"Karl Bringmann and Marvin K\u00fcnnemann. 2018. Multivariate fine-grained complexity of longest common subsequence. In SODA. SIAM, 1216\u20131235."},{"key":"e_1_3_4_23_2","first-page":"979","volume-title":"FOCS","author":"Chakraborty Diptarka","year":"2018","unstructured":"Diptarka Chakraborty, Debarati Das, Elazar Goldenberg, Michal Kouck\u00fd, and Michael E. Saks. 2018. Approximating edit distance within constant factor in truly sub-quadratic time. In FOCS. IEEE, 979\u2013990."},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/146637.146650"},{"key":"e_1_3_4_25_2","first-page":"1101","volume-title":"FOCS","author":"Goldenberg Elazar","year":"2019","unstructured":"Elazar Goldenberg, Robert Krauthgamer, and Barna Saha. 2019. Sublinear algorithms for gap edit distance. In FOCS. IEEE, 1101\u20131120."},{"key":"e_1_3_4_26_2","first-page":"1181","volume-title":"SODA","author":"Hajiaghayi MohammadTaghi","year":"2019","unstructured":"MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Xiaorui Sun. 2019. Approximating LCS in linear time: Beating the \\(\\sqrt {n}\\) barrier. In SODA. SIAM, 1181\u20131200."},{"key":"e_1_3_4_27_2","article-title":"Approximating LCS in linear time: Beating the  \\(\\surd\\) n barrier","volume":"2003","author":"Hajiaghayi MohammadTaghi","year":"2020","unstructured":"MohammadTaghi Hajiaghayi, Masoud Seddighin, Saeed Seddighin, and Xiaorui Sun. 2020. Approximating LCS in linear time: Beating the \\(\\surd\\) n barrier. CoRR abs\/2003.07285.","journal-title":"CoRR"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/359581.359603"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-008-9101-6"},{"key":"e_1_3_4_31_2","first-page":"699","volume-title":"STOC","author":"Kouck\u00fd Michal","year":"2020","unstructured":"Michal Kouck\u00fd and Michael E. Saks. 2020. Constant factor approximations to edit distance on far input pairs in nearly linear time. In STOC. ACM, 699\u2013712."},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840446"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264437"},{"key":"e_1_3_4_35_2","first-page":"1121","volume-title":"FOCS","author":"Rubinstein Aviad","year":"2019","unstructured":"Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun. 2019. Approximation algorithms for LCS and LIS with truly improved running times. In FOCS. IEEE, 1121\u20131145."},{"key":"e_1_3_4_36_2","first-page":"1591","volume-title":"SODA","author":"Rubinstein Aviad","year":"2020","unstructured":"Aviad Rubinstein and Zhao Song. 2020. Reducing approximate longest common subsequence to approximate edit distance. In SODA. SIAM, 1591\u20131600."},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90035-V"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568398","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3568398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:33Z","timestamp":1750182693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3568398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3568398"],"URL":"https:\/\/doi.org\/10.1145\/3568398","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"2021-06-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}