6
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Thanks for the pointer to the FFT. By "slightly larger" than quadratic what exactly do you refer to? If the range is $m=2n^3+1,$ as it is here the FFT complexity is $O(n^3 \log n)$ but the naive search complexity of forming pairs from $A,B$ and looking sums up in $C$ is still $O(n^2)$. $\endgroup$
    – kodlu
    Commented Jul 10, 2020 at 0:04
  • 2
    $\begingroup$ The bound $2n^3+1$ is polynomial in $n$, whereas it is not at all obvious that the problem could be reduced even to subexponential-sized numbers. That's why it's impressive. This is why Sariel calls the numbers "slightly" larger than quadratic. $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Jul 10, 2020 at 6:54
  • 1
    $\begingroup$ Yes. FFT is no longer relevant if the numbers are bigger than $n^2$, but it says something about the problem: The problem is easy if the numbers are small. As such, the question becomes, how large the numbers have to be before the problem becomes quadratic? As a constructive example consider subset sum - it is an NP Complete/Hard problem, but only if the numbers are exponentially large... $\endgroup$
    – Sariel Har-Peled
    Commented Jul 11, 2020 at 4:33
  • 1
    $\begingroup$ Thanks Sariel, that's clearer to me now. $\endgroup$
    – kodlu
    Commented Jul 11, 2020 at 4:49
4
$\begingroup$

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!

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.