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>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 "obvious" in your comments and answers.
