Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility

DOI10.1145/2840728.2840746zbMATH Open1334.68079OpenAlexW2294619171MaRDI QIDQ2800573FDOQ2800573

Authors: Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, Stefan Schneider, Marco L. Carmosino 

Publication date: 15 April 2016

Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2840728.2840746

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

zbMATH Keywords

computational complexitynondeterminismall-pairs shortest pathSETH3-sumconditional lower boundsfine-grained complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (34)

• Nontriviality for exponential time w.r.t. weak reducibilities
• Subquadratic algorithms for algebraic 3SUM
• Strong time bounds: Non-computable bounds and a hierarchy theorem
• Fine-grained complexity theory: conditional lower bounds for computational geometry
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• Scheduling lower bounds via AND subset sum
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Title not available (Why is that?)
• A hierarchy theorem for interactive proofs of proximity
• Simple doubly-efficient interactive proof systems for locally-characterizable sets
• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• Title not available (Why is that?)
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Maximum matching in almost linear time on graphs of bounded clique-width
• Logical Approaches to Computational Barriers
• More consequences of falsifying SETH and the orthogonal vectors conjecture
• Towards hardness of approximation for polynomial time problems
• The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
• \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
• Strong extension axioms and Shelah's zero-one law for choiceless polynomial time
• Efficiently enumerating hitting sets of hypergraphs arising in data profiling
• A short note on Merlin-Arthur protocols for subset sum
• Nontriviality for Exponential Time w.r.t. Weak Reducibilities
• \(k\)-SUM in the sparse regime: complexity and applications
• Fine-Grained Complexity Theory (Tutorial)
• Indistinguishability obfuscation, range avoidance, and bounded arithmetic
• Conditional hardness for sensitivity problems
• Detecting communities is hard (and counting them is even harder)
• The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
• Title not available (Why is that?)
• The fine-grained complexity of multi-dimensional ordering properties

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)