Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility

DOI10.1145/2840728.2840746zbMath1334.68079OpenAlexW2294619171MaRDI QIDQ2800573

Jiawei Gao, Ivan Mihajlin, Russell Impagliazzo, 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

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)

Related Items

Scheduling lower bounds via AND subset sum ⋮ Matching Triangles and Basing Hardness on an Extremely Popular Conjecture ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ A short note on Merlin-Arthur protocols for subset sum ⋮ Subquadratic algorithms for succinct stable matching ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ Unnamed Item ⋮ Improved Merlin-Arthur protocols for central problems in fine-grained complexity ⋮ Unnamed Item ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Efficiently enumerating hitting sets of hypergraphs arising in data profiling ⋮ 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 ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy ⋮ The fine-grained complexity of multi-dimensional ordering properties ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fine-grained complexity theory: conditional lower bounds for computational geometry