The Complexity of Problems in P Given Correlated Instances

DOI10.4230/LIPIcs.ITCS.2017.13zbMath1403.68081OpenAlexW2772748234MaRDI QIDQ4638062

Dhiraj Holden, Shafi Goldwasser

Publication date: 3 May 2018

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

zbMATH Keywords

longest common subsequencefine-grained complexitycorrelated instances

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Dynamic programming (90C39) Algorithms on strings (68W32)

Cites Work

• On a class of \(O(n^ 2)\) problems in computational geometry
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• The Computational Benefit of Correlated Instances
• The smoothed complexity of edit distance
• Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
• A fast algorithm for computing longest common subsequences
• Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
• Probability and Computing
• Algorithms and Data Structures
• On the complexity of \(k\)-SAT

This page was built for publication: The Complexity of Problems in P Given Correlated Instances