What are the relationships between those hypotheses in Fine-Grained Complexity Theory?

Question

Complexity theory, through such concepts as NP-completeness, distinguishes between computational problems that have relatively efficient solutions and those that are intractable. "Fine-grained" complexity aims to refine this qualitative distinction into a quantitative guide as to the exact time required to solve problems. More details can be found here: http://simons.berkeley.edu/programs/complexity2015

Here are some important hypotheses:

ETH: $3$-$SAT$ requires $2^{\delta n}$ time for some $ \delta > 0$.

SETH: for every $\varepsilon > 0$, there is a $k$ such that $k$-$SAT$ on $n$ variables, $m$ clauses cannot be solved in $2^{(1-\varepsilon)n}~poly~m$ time.

It is known that SETH is stronger than ETH and they both are stronger than $P \neq NP$,and both stronger than $FTP\neq W[1]$.

Four other important conjectures:

1. 3SUM Conjecture: 3SUM on $n$ integers in $\{-n^3,…,n^3\}$ requires $n^{2-o(1)}$ time

2. OV Conjecture: Orthogonal vectors on $n$ vectors requires $n^{2-o(1)}$ time.

3. APSP Conjecture: All Pairs Shortest Path on $n$ nodes and $O(\log n)$ bit weights requires $n^{3-o(1)}$ time.

4. BMM Conjecture: Any "combinatorial" algorithm for Boolean matrix multiplication requires $n^{3-o(1)}$ time.

It is known that SETH implies the OV Conjecture (Ryan Willams, 2004). Besides Ryan’s proof that SETH $\implies$ OV Conjecture, there are no other reductions relating the conjectures known.

My question: Do you know other related hypotheses or conjectures in this area? What are the relationships between them?

Acknowledgement: results listed are from the slides of Virginia Vassilevska Williams, she also gave me partial answers to this question.

Link to slides: http://theory.stanford.edu/~virgi/overview.pdf

Answer 1

This is a recent paper introducing Nondeterministic Strong Exponential Time Hypothesis (NSETH), which is an extension of SETH.

NSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT cannot be solved in nondeterministic time $2^{(1-\epsilon)n}$.

NSETH implies SETH. If NSETH is true, then some problems do not have SETH lower bounds (because they have nondeterministic algorithms faster than deterministic algorithms).

This paper also introduced Non-uniform Nondeterministic Strong Exponential Time Hypothesis (NUNSETH), a hypothesis stronger than NSETH and SETH.

NUNSETH: For every $\epsilon >0$, there is a $k$ such that $k$-DNF-TAUT cannot be recognized by nondeterministic circuit families of size $2^{(1-\epsilon)n}$.

Answer 2

Another interesting conjecture is hardness of $k$-Clique for fixed $k$ (see here).

This isn't exactly the sort of relationship you're looking for, but there was an interesting FOCS paper showing that a natural problem called "Matching Triangles" is hard under any of the SETH, 3SUM, or APSP conjectures (see here). It is not currently known whether or not any of these three conjectures imply each other in any interesting way -- this is one of the major open questions of Fine-Grained Complexity.

Answer 3

relatively recent results by Backurs, Indyk accepted to STOC 2015 that computing edit distance in $O(n^{2-\epsilon})$ time → SETH false tie in neatly/ strong to the new emerging "fine grained complexity" research program/ paradigm. they are closely related to/ built on Williams result that SETH → Orthogonal Vectors conjecture. (even covered by the mainstream media, Boston Globe).

• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)/ Backurs, Indyk

• A New Map Traces the Limits of Computation/ Pavlus, Quanta magazine

• For 40 years, computer scientists looked for a solution that doesn’t exist / Boston Globe

• Puzzling Evidence / RJLipton blog

a seemingly very similar result due to Wehar considers the "2 DFA intersection emptiness" problem and finds that $O(n^{2-\epsilon})$ time → SETH false.

• Deciding emptiness of intersection of regular languages in subquadratic time/ cstheory SE

Wehar has other results that seem to also fit into general "fine grained complexity" connections, that the same $k$ DFA intersection emptiness in $n^{o(k)}$ time → $NL \subsetneq P$

• Hardness Results for Intersection Non-Emptiness/ Wehar

along these lines it is also worth mentioning there is a known significant connection between DFA constructions and Levenshtein distance calculations eg in this paper

• Fast string correction with Levenshtein automata/ Shulz, Mihov