3SUM Complexity—A special(?) Case In the paper “Consequences of Faster Alignment of Sequences” by
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann which appeared in ICALP 2014 and is available here the following version of the integer 3-SUM conjecture is stated.
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.$
Not being an expert I have the following question.
How is this restriction to the set of integers with absolute value $\leq n^3$ justified? Is this in some sense hardest and other cases can be solved if this case is solved?
Remark: I suppose a ground set of size $O(n^3)$ is dense in the sense that a lot of triple candidates cannot be ruled out, but I imagine there are more spread out sets which may have similar properties.
Edit 2: Changed the focus of the question.
The smaller this upper bound is, the easier the problem becomes. In particular, if the range is $m$, then the problem can be solved in $O(m \log m)$ time using FFT. It is impressive/interesting that the authors were able to show that the problem is still quadratically nasty for numbers that are &quot;slightly&quot; larger than quadratic.