Deterministic Longest Common Subsequence Approximation in Near-Linear Time
Itai Boneh, Shay Golan, Matan Kraus · 2025
Read Deterministic Longest Common Subsequence Approximation in Near-Linear Time by Itai Boneh, Shay Golan, Matan Kraus (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22486.txt.
Introduction
Itai Boneh, Shay Golan, and Matan Kraus give, in 2025, a fast deterministic method for estimating the longest common subsequence of two long strings. That shared subsequence, a classic target in computer science, is expensive to compute exactly. Randomized approximations existed, but a deterministic one with a strong guarantee and near-linear running time did not.
Their algorithm always returns the same answer for the same input, runs in near-linear time, and guarantees an approximation within a factor that grows slower than the input length. The authors note it is the first deterministic method to combine a sublinear approximation ratio with near-linear speed.
Catalog record
| CREATOR | Itai Boneh, Shay Golan, Matan Kraus |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 34 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-22486
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Deterministic Longest Common Subsequence Approximation in Near-Linear Time Itai Boneh, Shay Golan, Matan Kraus Abstract We provide a deterministic algorithm that outputs an O ( n 3 / 4 log n ) O(n^{3/4}\log n) -approximation for the Longest Common Subsequence (LCS) of two input sequences of length n n in near-linear time. This is the first deterministic approximation algorithm for LCS that achieves a sub-linear approximation ratio in near-linear time. \crefname algocflinelinelines \Crefname algocflineLineLines \crefname problemctrProblemProblems \crefname claimClaimClaims \crefname observationObservationObservations Reichman University and University of Haifa, Israel and https://sites.google.com/view/itai-boneh/home-page [email protected]://orcid.org/0009-0007-8895-4069supported by Israel Science Foundation grant 810/21. Reichman University and University of Haifa, Israel and https://sites.google.com/view/shaygolan [email protected]://orcid.org/0000-0001-8357-2802supported by Israel Science Foundation grant 810/21. Bar Ilan Univesity, [email protected]://orcid.org/0000-0002-2989-1113supported by the ISF grant no. 1926/19, by the BSF grant 2018364, and by the ERC grant MPM under the EU’s Horizon 2020 Research and Innovation Programme (grant no. 683064). ccs Theory of computation Design and analysis of algorithms keywords Longest Common Subsequence, Approximation Algorithms, Longest Increasing Subsequence † † runningauthor: Boneh, Golan and Kraus † † copyright: Jane Open Access and Joan R. Public † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The Longest Common Subsequence ( \mathsf{LCS} ) problem is a classic string comparison task, whose standard dynamic programming solution is a staple of introductory computer science curricula. The \mathsf{LCS} problem and its variations have been studied extensively over the past decades, including in works such as [ WF74 , AHU76 , Hir77 , HS77 , MP80 , NKY82 , Apo86 , Mye86 , AG87 , EGGI92 , BHR00 , IR09 , ABW15 , BK15 , AHWW16 , BK18 , AB18 , RSSS19 , RS20 , HSSS19 ] . Given two sequences, the goal is to find a longest sequence that appears as a subsequence in both, a task fundamental to understanding similarity and structure in discrete data. Classical algorithms solve \mathsf{LCS} in quadratic time, specifically O(n^{2}) for sequences of length n , using dynamic programming [ WF74 , Hir75 ] . However, despite decades of research, improving this bound to truly subquadratic time remains elusive, with conditional lower bounds based on the Strong Exponential Time Hypothesis (SETH) suggesting that no truly subquadratic algorithm exists for general instances [ ABW15 ] . These hardness results underscore the intrinsic complexity of \mathsf{LCS} and motivate the exploration of approximation algorithms and specialized cases to circumvent these barriers. In this work, we consider the problem of approximating \mathsf{LCS}(x,y) of two input sequences x and y in near-linear time. Specifically, the goal is to output a common subsequence of x and y whose length approximates the length of a longest common subsequence. For sequences over a binary alphabet, it is trivial to obtain a 1/2 -approximation for \mathsf{LCS}(x,y) . This trivial 1/2 -approximation ratio remained the best known in this setting until recently, when Rubinstein and Song [ RS20 ] showed that a slightly better approximation ratio can be achieved for binary sequences of the same length. The approximation algorithm of Rubinstein and Song is essentially a reduction to Edit Distance approximation. When plugging in the state-of-the-art Edit Distance approximation algorithm by Andoni and Nosatzki [ AN20 ] , their algorithm achieves a 1/2+\varepsilon approximation ratio in near-linear time. Subsequently, Akmal and Vassilevska Williams [ AV21 ] presented a subquadratic-time algorithm achieving a better-than- 1/2 approximation ratio even when the input sequences are allowed to have different lengths. They further generalized their result to obtain a subquadratic algorithm that achieves an approximation ratio better than 1/k for sequences over an alphabet of size k . However, for general alphabets, the algorithms of [ RS20 , AV21 ] do not yield an approximation ratio polynomially better than 1/n , a trivial guarantee obtainable by selecting a single common character. In the fully general setting, where no assumptions are made about the alphabet size, a folklore algorithm achieves an O(\sqrt{n}) -approximation 1 1 1 There is some discrepancy in the literature regarding how to denote the approximation ratio of an algorithm. In works on small alphabets, the term ‘ \alpha -approximation’ typically refers to an algorithm that returns a common subsequence of length at least \alpha L , where L is the length of the longest common subsequence. In contrast, works on general input sequences often refer to an ‘ X -approximation’ as an algorithm that returns a subsequence of length at least L/X . We adopt the latter convention for the rest of this paper. in \tilde{O}(n) time 2 2 2 Throughout this paper, \tilde{O}(f(n))=O(f(n)\cdot{\mathsf{polylog}}n) . . More recently, Hajiaghayi, Seddighin, and Seddighin and Sun [ HSSS22 ] presented a linear-time algorithm that achieves a slightly better approximation ratio of O(n^{0.497956}) . Shortly thereafter, Bringmann, Cohen-Addad and Das [ BCD23 ] proposed an improved algorithm, offering an O(n^{0.4}) -approximation with similar running time. Interestingly, all known near-linear time algorithms for approximating \mathsf{LCS} in the general setting, where the alphabet may be arbitrarily large, are inherently randomized. This includes the folklore O(\sqrt{n}) -approximation. Despite the fundamental nature of the \mathsf{LCS} problem and the significant attention its approximation has received in recent years, no deterministic near-linear time approximation algorithm is known. We present an algorithm with \tilde{O}(n) running time, where n=|x|+|y| is the total length of the input sequences, that outputs an O(n^{3/4}\log n) -approximation of \mathsf{LCS}(x,y) . This is the first \mathsf{LCS} approximation algorithm to achieve a non-trivial approximation ratio in near-linear time without relying on randomness. Our result is summarized in the following theorem. Theorem 1 . There is a deterministic algorithm that receives two input sequences x and y with n=|x|+|y| , and returns in \tilde{O}(n) time a common subsequence L of x and y such that |L|\geq|\mathsf{LCS}(x,y)|/(n^{3/4}\log n) . In \cref sec:prelim, we present useful notation and pre-existing tools. In \cref sec:Warm-up, we present a simplified version of our main algorithm achieving an O(n^{4/5}) -approximation. This version illustrates our novel technique, Greedy LDS peeling, that allows us to approximate \mathsf{LCS} deterministically. In \cref sec:main we enhance the simplified algorithm to finally obtain the O(n^{3/4}\log n) -approximation and prove \cref thm:main. 2 Preliminaries For a natural number n\in\mathbb{N} , we denote [n]=\{1,2,\dots,n\} . We also denote consecutive ranges of integers as \{a,a+1,\ldots b\}=[a..b] . Throughout this paper, we denote the set of symbols in the input sequences as \Sigma . We denote a sequence x over an alphabet \Sigma as x=x_{1},x_{2},\dots,x_{|x|} . Given a sequence x we say that \hat{x}=x_{i_{1}},x_{i_{2}},\dots,x_{i_{k}} is a subsequence of x if i_{1}<i_{2}<\dots<i_{k} . Given two sequences x and y , we say that z is a common subsequence of x and y if z is a subsequence of x and also a subsequence of y . We say that z is a longest common subsequence ( \mathsf{LCS} ) of x and y if for every \hat{z} that is a common subsequence of x and y , it holds that |z|\geq|\hat{z}| . We denote \mathsf{LCS}(x,y) as some longest common subsequence of