Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
From MaRDI portal
(Redirected from Publication:2800573)
Recommendations
- On problems as hard as CNF-SAT
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Which problems have strongly exponential complexity?
- Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis
Cited in
(50)- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- Efficiently enumerating hitting sets of hypergraphs arising in data profiling
- The fine-grained complexity of multi-dimensional ordering properties
- Maximum matching in almost linear time on graphs of bounded clique-width
- Fine-grained complexity theory: conditional lower bounds for computational geometry
- Scheduling lower bounds via AND subset sum
- Subquadratic algorithms for algebraic 3SUM
- scientific article; zbMATH DE number 4205978 (Why is no real title available?)
- A short note on Merlin-Arthur protocols for subset sum
- Nontriviality for Exponential Time w.r.t. Weak Reducibilities
- Nontriviality for exponential time w.r.t. weak reducibilities
- Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Towards hardness of approximation for polynomial time problems
- Conditional hardness for sensitivity problems
- A hierarchy theorem for interactive proofs of proximity
- Detecting communities is hard (and counting them is even harder)
- scientific article; zbMATH DE number 4119625 (Why is no real title available?)
- Simple doubly-efficient interactive proof systems for locally-characterizable sets
- On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
- Fine-Grained Complexity Theory (Tutorial)
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
- Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
- Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
- New algorithms and lower bounds for all-pairs max-flow in undirected graphs
- The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Logical Approaches to Computational Barriers
- Improved Merlin-Arthur protocols for central problems in fine-grained complexity
- Indistinguishability obfuscation, range avoidance, and bounded arithmetic
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- \(k\)-SUM in the sparse regime: complexity and applications
- On Wagner's k-tree algorithm over integers
- Scheduling lower bounds via and subset sum
- Hardness of approximate diameter: now for undirected graphs
- Certificates in P and subquadratic-time computation of radius, diameter, and all eccentricities in graphs
- Fine-grained complexity in a world without cryptography
- (Inefficient prover) ZAPs from hard-to-invert functions
- Applications of random algebraic constructions to hardness of approximation
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- Polynomial formulations as a barrier for reduction-based hardness proofs
- On exponential-time hypotheses, derandomization, and circuit lower bounds
- Inapproximability of diameter in super-linear time: beyond the 5/3 ratio
- 4 vs 7 sparse undirected unweighted diameter is SETH-hard at time \(n^{4/3}\)
- From donkeys to kings in tournaments
- Improved space bounds for subset sum
- Does subset sum admit short proofs?
- Hardness of median and center in the Ulam metric
- Strong time bounds: Non-computable bounds and a hierarchy theorem
This page was built for publication: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800573)
