A framework of quantum strong exponential-time hypotheses
From MaRDI portal
Cites work
- A faster algorithm computing string edit distances
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An improved exponential-time algorithm for k -SAT
- An optimal quantum algorithm for the oracle identification problem
- Approximating edit distance in truly subquadratic time: quantum and MapReduce
- Approximating edit distance within constant factor in truly sub-quadratic time
- Consequences of Faster Alignment of Sequences
- Does looking inside a circuit help?
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Exponential Time Complexity of the Permanent and the Tutte Polynomial
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- Matching triangles and basing hardness on an extremely popular conjecture
- On problems as hard as CNF-SAT
- On the (im)possibility of obfuscating programs
- On the complexity of k-SAT
- Quadratic conditional lower bounds for string problems and dynamic time warping
- Quantum Complexity Theory
- Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language
- Quantum lower bounds by polynomials
- Quantum lower bounds by quantum arguments
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
- STACS 2004
- Strengths and Weaknesses of Quantum Computing
- Tight hardness results for LCS and other sequence similarity measures
- Which problems have strongly exponential complexity?
- Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
Cited in
(2)
This page was built for publication: A framework of quantum strong exponential-time hypotheses
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7231542)
