# Item

ITEM ACTIONSEXPORT

Released

Paper

#### A Linear-Time n0.4-Approximation for Longest Common Subsequence

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:2106.08195.pdf

(Preprint), 416KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Bringmann, K., Cohen-Addad, V., & Das, D. (2021). A Linear-Time n0.4-Approximation for Longest Common Subsequence. Retrieved from https://arxiv.org/abs/2106.08195.

Cite as: https://hdl.handle.net/21.11116/0000-0008-E267-5

##### Abstract

We consider the classic problem of computing the Longest Common Subsequence

(LCS) of two strings of length $n$. While a simple quadratic algorithm has been

known for the problem for more than 40 years, no faster algorithm has been

found despite an extensive effort. The lack of progress on the problem has

recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15]

and Bringmann and K\"unnemann [FOCS'15] who proved that there is no

subquadratic algorithm unless the Strong Exponential Time Hypothesis fails.

This has led the community to look for subquadratic approximation algorithms

for the problem.

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

$O(n^{\varepsilon/2})$-approximation algorithm with running time

$\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 <

\varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin,

Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a

$O(n^{0.497956})$-approximation in expectation; improving upon the naive

$O(\sqrt{n})$-approximation for the first time.

In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$

computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high

probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an

$\tilde{O}(n^{0.4})$-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 $O(n^{2-\varepsilon})$,

improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$,

and (3) instead of only in expectation, succeeds with high probability.

(LCS) of two strings of length $n$. While a simple quadratic algorithm has been

known for the problem for more than 40 years, no faster algorithm has been

found despite an extensive effort. The lack of progress on the problem has

recently been explained by Abboud, Backurs, and Vassilevska Williams [FOCS'15]

and Bringmann and K\"unnemann [FOCS'15] who proved that there is no

subquadratic algorithm unless the Strong Exponential Time Hypothesis fails.

This has led the community to look for subquadratic approximation algorithms

for the problem.

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

$O(n^{\varepsilon/2})$-approximation algorithm with running time

$\tilde{O}(n^{2-\varepsilon})$ has been known, for any constant $0 <

\varepsilon \le 1$. Recently, a breakthrough result by Hajiaghayi, Seddighin,

Seddighin, and Sun [SODA'19] provided a linear-time algorithm that yields a

$O(n^{0.497956})$-approximation in expectation; improving upon the naive

$O(\sqrt{n})$-approximation for the first time.

In this paper, we provide an algorithm that in time $O(n^{2-\varepsilon})$

computes an $\tilde{O}(n^{2\varepsilon/5})$-approximation with high

probability, for any $0 < \varepsilon \le 1$. Our result (1) gives an

$\tilde{O}(n^{0.4})$-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 $O(n^{2-\varepsilon})$,

improving upon the naive bound of $O(n^{\varepsilon/2})$ for any $\varepsilon$,

and (3) instead of only in expectation, succeeds with high probability.