<p>I believe I can partially answer your question as to why the bounds of <span class="math-container">$\{-n^3, ..., n^3\}$</span> are justified.</p>
<p>This <a href="https://people.csail.mit.edu/mip/papers/mp-3sum/paper.pdf" rel="nofollow noreferrer">paper</a> by Pătraşcu mentions that for 3SUM over any bounded universe of integers of size <span class="math-container">$u &gt;&gt; n^3$</span>, the universe size can be hashed down to <span class="math-container">$O(n^3)$</span> while maintaining the expected <span class="math-container">$O(n^2)$</span> run time for 3SUM. Therefore, to prove that 3SUM can be solved in expected time <span class="math-container">$O(n^{2 - \varepsilon})$</span> over every universe size <span class="math-container">$u$</span> of integers, it suffices to give an algorithm that solves 3SUM on every universe of size <span class="math-container">$O(n^3)$</span> in expected time <span class="math-container">$O(n^{2 - \varepsilon})$</span>.</p>
<p>Pătraşcu doesn't directly give this reduction, but states that the techniques of this <a href="https://people.csail.mit.edu/mip/papers/3sum/3sum.pdf" rel="nofollow noreferrer">paper</a> can be used to perform such a hashing.</p>
<p>I have been reading this paper, but I haven't quite figured out the details of this reduction.</p>
<p>I hope this helps!</p>

CC BY-SA 4.0
2020-07-12T01:25:08.173Z
2020-07-12T01:25:08.173Z
Gary Hoppenworth
<p>The smaller this upper bound is, the easier the problem becomes. In particular, if the range is <span class="math-container">$m$</span>, then the problem can be solved in <span class="math-container">$O(m \log m)$</span> 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.</p>

CC BY-SA 4.0
2020-07-10T00:04:57.300Z
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)$.
kodlu
CC BY-SA 4.0
2020-07-10T06:54:30.373Z
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.
Lieuwe Vinkhuijzen
CC BY-SA 4.0
2020-07-11T04:33:40.723Z
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...
Sariel Har-Peled
CC BY-SA 4.0
2020-07-11T04:49:19.907Z
Thanks Sariel, that's clearer to me now.
kodlu
CC BY-SA 4.0
2020-07-09T22:13:34.480Z
2020-07-09T22:13:34.480Z
Sariel Har-Peled
<p>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 <a href="https://people.csail.mit.edu/virgi/pubyear.html" rel="nofollow noreferrer">here</a> the following version of the integer 3-SUM conjecture is stated.</p>
<p><strong>Conjecture 1 (3-SUM Conjecture)</strong> <em>In the Word RAM model with words of <span class="math-container">$O(\log n)$</span> bits, any algorithm requires <span class="math-container">$n^{2−o(1)}$</span> time in expectation to determine whether three sets
<span class="math-container">$A,B,C \subset \{−n^3,\ldots,n^3\}$</span> with <span class="math-container">$|A| = |B| = |C| = n$</span>
integers contain three elements <span class="math-container">$a∈A,b∈B,c∈C$</span> with <span class="math-container">$a+b+c=0.$</span></em></p>
<p>Not being an expert I have the following question.</p>
<p>How is this restriction to the set of integers with absolute value <span class="math-container">$\leq n^3$</span> justified? Is this in some sense hardest and other cases can be solved if this case is solved?</p>
<p><strong>Remark:</strong> I suppose a ground set of size <span class="math-container">$O(n^3)$</span> 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.</p>
<p><strong>Edit 2:</strong> Changed the focus of the question.</p>

<cc.complexity-theory><ds.algorithms><time-complexity>
3SUM Complexity—A special(?) Case
kodlu
# 3SUM Complexity—A special(?) Case

(Asked by: username_0 on 2020-07-08)

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](https://people.csail.mit.edu/virgi/pubyear.html) 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.

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity


---

## 2 answers

### Answer by username_2 on 2020-07-09. Score: 6 | Accepted 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.

> **Comments:**
> **username_0**: 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)$.  
> **username_3**: 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.  
> **username_2**: 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...  
> **username_0**: Thanks Sariel, that's clearer to me now.  

---

### Answer by username_1 on 2020-07-12. Score: 4

I believe I can partially answer your question as to why the bounds of $\{-n^3, ..., n^3\}$ are justified.

This [paper](https://people.csail.mit.edu/mip/papers/mp-3sum/paper.pdf) 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](https://people.csail.mit.edu/mip/papers/3sum/3sum.pdf) 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!


---

