Towards hardness of approximation for polynomial time problems
From MaRDI portal
Recommendations
- Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
- Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
- Approximating LCS in Linear Time: Beating the √n Barrier
- Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
- On some fine-grained questions in algorithms and complexity
Cites work
- scientific article; zbMATH DE number 3597878 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- A fast and practical bit-vector algorithm for the longest common subsequence problem
- A faster algorithm computing string edit distances
- Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable
- Algorithms on Strings, Trees and Sequences
- Amplification and Derandomization without Slowdown
- Approximability of the discrete Fréchet distance
- Approximating the best Nash equilibrium in \(n^{o(\log n)}\)-time breaks the exponential time hypothesis
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Automata, Languages and Programming
- Better approximation algorithms for the graph diameter
- Consequences of Faster Alignment of Sequences
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Efficient learning algorithms yield circuit lower bounds
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Faster Deterministic and Las Vegas Algorithms for Offline Approximate Nearest Neighbors in High Dimensions
- Hardness of RNA folding problem with four symbols
- If the current clique algorithms are optimal, so is Valiant's parser
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- Improving exhaustive search implies superpolynomial lower bounds
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Incremental String Comparison
- Introduction to algorithms
- Local reductions
- Low distortion embeddings for edit distance
- Matching triangles and basing hardness on an extremely popular conjecture
- Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
- More applications of the polynomial method to algorithm design
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- Nonuniform ACC circuit lower bounds
- Oblivious string embeddings and edit distance approximations
- On a class of O(n^2) problems in computational geometry
- On hardness of jumbled indexing
- On problems as hard as CNF-SAT
- On the complexity of k-SAT
- On the hardness of partially dynamic graph problems and connections to diameter
- On the power of small-depth computation
- Performance analysis of some simple heuristics for computing longest common subsequences
- Polylogarithmic approximation for edit distance and the asymmetric query complexity
- Robust PSPs of proximity, shorter PSPs and applications to coding
- Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
- Short PCPs with Polylog Query Complexity
- Short PCPs with projection queries
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- Sparse RNA folding: time and space efficient algorithms
- Speedup of RNA pseudoknotted secondary structure recurrence computation with the four-Russians method
- Streaming algorithms for embedding and computing edit distance in the low distance regime
- Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
- Subcubic equivalences between graph centrality problems, APSP and diameter
- Subcubic equivalences between path, matrix, and triangle problems
- Subtree isomorphism revisited
- The complexity of satisfiability of small depth circuits
- Tighter connections between derandomization and circuit lower bounds
- Towards polynomial lower bounds for dynamic problems
- Turing machines that take advice
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Which problems have strongly exponential complexity?
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
Cited in
(25)- The complexity of polynomial-time approximation
- On solving hard problems by polynomial-size circuits
- On the hardness of approximate and exact (bichromatic) maximum inner product
- Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
- scientific article; zbMATH DE number 7758340 (Why is no real title available?)
- scientific article; zbMATH DE number 1206797 (Why is no real title available?)
- On the complexity of approximating the Hadwiger number
- Mathematical Foundations of Computer Science 2004
- Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
- Improved approximation for longest common subsequence over small alphabets
- A linear-time \(n^{0.4}\)-approximation for longest common subsequence
- Streaming and small space approximation algorithms for edit distance and longest common subsequence
- A Linear-Time n 0.4 -Approximation for Longest Common Subsequence
- The Complexity of Somewhat Approximation Resistant Predicates
- Exploring the approximability landscape of 3SUM
- Hardness of approximation in p via short cycle removal: cycle detection, distance oracles, and beyond
- scientific article; zbMATH DE number 7250154 (Why is no real title available?)
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- A Theory of NP-completeness and Ill-conditioning for Approximate Real Computations
- Approximation algorithms for LCS and LIS with truly improved running times
- On some fine-grained questions in algorithms and complexity
- Approximating longest common subsequence in linear time: beating the \(\sqrt{n}\) barrier
This page was built for publication: Towards hardness of approximation for polynomial time problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638059)
