Tight conditional lower bounds for longest common increasing subsequence

DOI10.4230/LIPICS.IPEC.2017.15zbMATH Open1443.68068MaRDI QIDQ5111874FDOQ5111874

Authors:

Publication date: 27 May 2020

Recommendations

• Tight conditional lower bounds for longest common increasing subsequence
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• Faster algorithms for computing longest common increasing subsequences
• Faster Algorithms for Computing Longest Common Increasing Subsequences
• Algorithms and Computation

zbMATH Keywords

parameterized complexitycombinatorial pattern matchingsequence alignmentsSETHfine-grained complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Which problems have strongly exponential complexity?
• Fast approximation algorithms for the diameter and radius of sparse graphs
• On the complexity of \(k\)-SAT
• A new algorithm for optimal 2-constraint satisfaction and its implications
• The String-to-String Correction Problem
• The longest common subsequence problem for arc-annotated sequences
• A faster algorithm computing string edit distances
• The constrained longest common subsequence problem
• An \(O(ND)\) difference algorithm and its variations
• On computing the length of longest increasing subsequences
• Fast computation of a longest increasing subsequence and application
• LCS\(k\): a refined similarity measure
• A fast algorithm for computing longest common subsequences
• On the generalized constrained longest common subsequence problems
• A simple algorithm for the constrained sequence problems
• ALGORITHMS FOR THE CONSTRAINED LONGEST COMMON SUBSEQUENCE PROBLEMS
• A fast algorithm for computing a longest common increasing subsequence
• The longest common subsequence problem revisited
• Constrained LCS: Hardness and Approximation
• Algorithms for the Longest Common Subsequence Problem
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Efficient polynomial-time algorithms for the constrained LCS problem with strings exclusion
• Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
• Faster algorithms for computing longest common increasing subsequences
• Efficient algorithms for finding a longest common increasing subsequence
• Consequences of Faster Alignment of Sequences
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Spelling correction in systems programs
• Multivariate fine-grained complexity of longest common subsequence
• A space efficient algorithm for the longest common subsequence in \(k\)-length substrings
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?
• A linear algorithm for 3-letter longest common weakly increasing subsequence
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• On problems equivalent to \((\min,+)\)-convolution
• Title not available (Why is that?)
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• New refinement techniques for longest common subsequence algorithms.

Cited In (4)

• Tight conditional lower bounds for longest common increasing subsequence
• Tighter connections between Formula-SAT and shaving logs
• Computing the longest common almost-increasing subsequence
• Why is it hard to beat \(O(n^2)\) for longest common weakly increasing subsequence?

This page was built for publication: Tight conditional lower bounds for longest common increasing subsequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111874)