Implication of solving 3SUM problem of a certain size on the Exponential Time Hypothesis In the recent question 3SUM Complexity—A special(?) Case I asked about why the set size $O(n^3)$ was an interesting value for the 3SUM Problem and got a nice answer. My reference was the paper “Consequences of Faster Alignment of Sequences” by
Abboud, Vassilevska Williams, and Weimann available [here][1]. The term of a certain size in the title of this question refers to the support set being $\{-n^3,\ldots,n^3\}$:
Conjecture 1 (3-SUM Conjecture) In the Word RAM model with words of $O(\log n)$ bits, any algorithm requires $n^{2−o(1)}$ time in expectation to determine whether three sets
$A,B,C \subset \{−n^3,\ldots,n^3\}$ with $|A| = |B| = |C| = n$
integers contain three elements $a∈A,b∈B,c∈C$ with $a+b+c=0.$
If there was an algorithm solving this exact version of 3SUM with complexity $O(n^{2-\varepsilon})$ for $\varepsilon&gt;0,$ what would be the impact on the Exponential Time Hypothesis?
Again, not being an expert, I am wondering would the ETH be refuted? Or the strong ETH only? Please feel free to include details that may be &quot;obvious&quot; in your comments and answers.
I think currently it is not even known if strong ETH and 3SUM are related, see e.g. [1]. For the relation of ETH and 3SUM, note that ETH really cannot be refuted by improving polynomial time algorithms (at least via Karp reductions) because it would only improve constants in the exponent of the runtime. In particular, if we reduce 3-SAT to a 3SUM instance of size $2^{O(n)}$, it will not refute ETH, and if we reduce 3-SAT to a 3SUM instance of size $2^{o(n)}$, it will refute ETH regardless of the complexity of 3SUM.
[1] Virginia V. Williams. Hardness of easy problems: Basing hardness on popular conjectures such as the strong exponential time hypothesis (invited talk). IPEC 2015. https://drops.dagstuhl.de/opus/volltexte/2015/5568/pdf/5.pdf