The Complexity of Problems in P Given Correlated Instances
From MaRDI portal
Recommendations
- On the classification of NP-complete problems in terms of their correlation coefficient
- Correlation decay and tractability of CSPs
- Correlation of NP-sets and co-NP-sets with respect to a random oracle
- Extension complexity of the correlation polytope
- scientific article; zbMATH DE number 3874610
- The complexity of the co-occurrence problem
- On the complexity of approximating the independent set problem
- The exact complexity of the infinite Post Correspondence Problem
- A short proof that the extension complexity of the correlation polytope grows exponentially
- On correlation polynomials and subword complexity
Cites work
- A fast algorithm for computing longest common subsequences
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- On a class of \(O(n^ 2)\) problems in computational geometry
- On the complexity of k-SAT
- Probability and Computing
- Smoothed analysis. Motivation and discrete models
- The Computational Benefit of Correlated Instances
- The smoothed complexity of edit distance
Cited in
(3)
This page was built for publication: The Complexity of Problems in P Given Correlated Instances
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638062)
