An n8/5+o(1)-Time Omega(lambda3)-Approximation for Longest Common Subsequence

Zhao Song

In the authors' words

Let $λ$ denote the ratio of the length of a longest common subsequence of two length- $n$ strings to $n$ . Rubinstein, Seddighin, Song and Sun [RSSS19] gave an $Ω (λ^{3})$ -approximation for LCS running in $O (n^{39/20})$ time, where $39/20 = 1.95$ . Song [Son19] mentioned that improving the $n^{1.95}$ running time is an interesting open question. We give an algorithm that computes an $Ω (λ^{3})$ -approximation of the longest common subsequence in $n^{8/5 + o (1)}$ time. This improves the exponent $1.95$ to $1.6 + o (1)$ .

Main resultThe abstract does not state a limitation.

An n8/5+o(1)-Time Ω(λ3)-Approximation for Longest Common Subsequence

In the authors' words

More on Algorithms & complexity that day

An Optimal Structure for All-Pairs Nearest Mincuts and Sensitivity Oracles for Edge Insertions

KnottedGraph: Scalable knotted-graph topology for scientific and mathematical discovery

Simulation-Efficient Analog Circuit Yield Optimization via Monte Carlo Zeroth-Order Gradient Estimation

From Segments to Trajectories: Evolving Affective Graphs with Evidence Retrieval for Continuous EEG Emotion Recognition

A 120-State Binary Turing Machine Equivalent to the Riemann Hypothesis

An $n^{8/5 + o (1)}$ -Time $Ω (λ^{3})$ -Approximation for Longest Common Subsequence