Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds

DOI10.4230/LIPIcs.ITCS.2018.35zbMath1462.68239OpenAlexW2782583418MaRDI QIDQ4993300

Aviad Rubinstein, Amir Abboud

Publication date: 15 June 2021

Full work available at URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.35

zbMATH Keywords

longest common subsequencecircuit lower boundsstrong exponential time hypothesisfine-grained complexitydistributed PCP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Algorithms on strings (68W32) Networks and circuits as models of computation; circuit complexity (68Q06)

Related Items (9)

Computing the longest common almost-increasing subsequence ⋮ Approximating Longest Common Subsequence in Linear Time: Beating the $\sqrt{{n}}$ Barrier ⋮ A Linear-Time n ^0.4 -Approximation for Longest Common Subsequence ⋮ Longest Common Subsequence with Gap Constraints ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A \#SAT algorithm for small constant-depth circuits with PTF gates

Uses Software

• PSI-BLAST
• BLAST

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Performance analysis of some simple heuristics for computing longest common subsequences
• Which problems have strongly exponential complexity?
• A fast and practical bit-vector algorithm for the longest common subsequence problem
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Algebrization
• Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity
• Interactive Oracle Proofs
• Local Reductions
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• Interactive PCP
• Oblivious string embeddings and edit distance approximations
• Interactive Locking, Zero-Knowledge PCPs, and Unconditional Cryptography
• Incremental String Comparison
• Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• Consequences of Faster Alignment of Sequences
• Short PCPs with Projection Queries
• Constant-round interactive proofs for delegating computation
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Streaming algorithms for embedding and computing edit distance in the low distance regime
• The PCP theorem by gap amplification
• Low distortion embeddings for edit distance
• On the complexity of \(k\)-SAT

This page was built for publication: Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds