Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?

DOI10.1016/j.ipl.2017.11.007zbMath1426.68103arXiv1703.01143OpenAlexW2949447832WikidataQ112162232 ScholiaQ112162232MaRDI QIDQ1705641

Peng Zhang

Publication date: 16 March 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1703.01143

zbMATH Keywords

computational complexitylower boundlongest common weakly increasing subsequenceSETH

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items

A Faster Subquadratic Algorithm for the Longest Common Increasing Subsequence Problem, Tight conditional lower bounds for longest common increasing subsequence, Unnamed Item

Cites Work

• Unnamed Item
• Faster algorithms for computing longest common increasing subsequences
• A fast algorithm for computing a longest common increasing subsequence
• A linear space algorithm for computing a longest common increasing subsequence
• A faster algorithm computing string edit distances
• A linear algorithm for 3-letter longest common weakly increasing subsequence
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Computational Complexity
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made