3SUM Complexity—A special(?) Case

Question

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.

Gary Hoppenworth · Answer

I believe I can partially answer your question as to why the bounds of ${-n^3, ..., n^3}$ are justified.
This paper by Pătraşcu mentions that for 3SUM over any bounded universe of integers of size $u >> n^3$, the universe size can be hashed down to $O(n^3)$ while maintaining the expected $O(n^2)$ run time for 3SUM. Therefore, to prove that 3SUM can be solved in expected time $O(n^{2 - varepsilon})$ over every universe size $u$ of integers, it suffices to give an algorithm that solves 3SUM on every universe of size $O(n^3)$ in expected time $O(n^{2 - varepsilon})$.
Pătraşcu doesn't directly give this reduction, but states that the techniques of this paper can be used to perform such a hashing.
I have been reading this paper, but I haven't quite figured out the details of this reduction.
I hope this helps!

Sariel Har-Peled · Answer

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 "slightly" larger than quadratic.

Answered by Sariel Har-Peled on October 30, 2021

3SUM Complexity—A special(?) Case

2 Answers

Add your own answers!

Ask a Question