<p>The first paper essentially gives a subquadratic algorithm if we know that every input number has $w$ bits and we can add two $w$ bit numbers in one step. This was not a very surprising result and it did not rule out an $\Omega(n^2)$ bound.</p>

<p>The second paper does not use any such assumptions and improves the exponent of $n$ for decision trees, which is a surprise, although not as big as it would be for all algorithms, for which they have only improved slightly (thus disproving the strongest conjecture). I would guess that more results will follow shortly.</p>

CC BY-SA 3.0
2014-04-07T02:03:58.000Z
I am happy with both answers, but could only accept one, so I accepted the more detailed one.
kodlu
CC BY-SA 3.0
2014-04-05T02:55:56.323Z
2014-04-05T02:55:56.323Z
domotorp
<p>Here are some points that help give perspective to the new results. </p>

<p>The decision tree complexity result is big. One line of attack (and Jeff Erickson can say more on this) was to try and lower bound 3SUM via looking at the decision complexity of the problem (i.e the number of comparisons needed to solve the problem). The hope was that something close to $\Omega(n^2)$ was attainable. </p>

<p>This result decisively trashes that argument with a $O(n^{3/2})$ bound. Note that this doesn't say anything about the true complexity of the problem. It says that a decision tree lower bound isn't going to happen. And that (along with other evidence) casts doubt on the basic premise that 3SUM is "morally" close to $n^2$. </p>

<p>The algorithmic result is subquadratic unconditionally (i.e not in a word-parallel model). That is a big deal, although I suppose one might quibble about the fact that it's not $O(n^{2-\epsilon})$ for some constant $\epsilon$. </p>

<p>As @domotorp says, this could very well be the beginning of a a series of new results. It's really hard to say. The current upper bound comes from "re-implementing" the decision tree algorithm with some magic tricks from Timothy Chan. It's conceivable that this could be pushed further. </p>

CC BY-SA 3.0
2014-04-06T03:53:31.970Z
_Jeff Erickson can say more on this_ — Not much more to say, really. I proved that a natural decision tree model requires depth $\Omega(n^2)$; the new paper shows that with a very slighty stronger model, depth $O(n^{3/2})$ is enough. In retrosect, this result shouldn't be surprising, in light of Fredman's and Chan's results on sorting X+Y and shortest paths. But it does completely close off a natural line of attack. As I told Seth, I'm simultaneously incredibly relieved and incredibly jealous.
Jeffε
CC BY-SA 3.0
2014-04-05T04:38:50.067Z
2014-04-05T04:38:50.067Z
Suresh Venkat
<p>The paper "Subquadratic Algorithms for 3SUM", by Ilya Baran, Erik D. Demaine, Mihai Patrascu has the following complexity for the </p>

<p><strong>3SUM problem:</strong> <em>given a list $L$ of $n$ integers if there are $x,y,z \in L$ such that $x+y=z.$</em></p>

<p>They state, "On a standard word RAM with $w-$bit words, we obtain a running time of 
$O(n^2/ \max\{w \log w, \log n (\log \log n)^2 \})$. In the circuit RAM with one nonstandard $AC0$ operation, we obtain $O(n^2/ w^2 \log w)$. In external memory, we achieve $O(n^2/(MB))$, even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of $O(n^2/ MB \log M )$. In all cases, our speedup is almost quadratic in the “parallelism” the model can aﬀord, which may be the best possible. See the Baran, Demaine, Patrascu paper <a href="http://erikdemaine.org/papers/3SUM_Algorithmica/paper.pdf">here</a>.</p>

<p>Recently, a paper "Threesomes, Degenerates, and Love Triangles" by Grondlund and Pettie has proved that "the decision tree complexity of 3SUM is $O(n^{3/2}\sqrt{\log n})$,  and that there is a randomized 3SUM algorithm running in $O(n^2(\log \log n)^2/\log n)$ time, and a deterministic algorithm running in $O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$ time. </p>

<p>These results refute the strongest version of the 3SUM conjecture, namely that its decision tree (and algorithmic) complexity is $Ω(n^2)$." </p>

<p>See this second paper <a href="http://arxiv.org/abs/1404.0799">here</a>.</p>

<p>Clearly, both are important papers. Not being an expert to this area, my question is about how to compare the impact and significance of either, given the different complexity models. Any other insightful comments about this problem is also welcome. For example had the first paper already ruled out the $\Omega(n^2)$ bound? </p>

<cc.complexity-theory><ds.algorithms>
Comparing Two Algorithms for 3SUM problem over Integers
kodlu
# Comparing Two Algorithms for 3SUM problem over Integers

(Asked by: username_0 on 2014-04-05)

The paper "Subquadratic Algorithms for 3SUM", by Ilya Baran, Erik D. Demaine, Mihai Patrascu has the following complexity for the

**3SUM problem:** *given a list $L$ of $n$ integers if there are $x,y,z \in L$ such that $x+y=z.$*

They state, "On a standard word RAM with $w-$bit words, we obtain a running time of
$O(n^2/ \max\{w \log w, \log n (\log \log n)^2 \})$. In the circuit RAM with one nonstandard $AC0$ operation, we obtain $O(n^2/ w^2 \log w)$. In external memory, we achieve $O(n^2/(MB))$, even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of $O(n^2/ MB \log M )$. In all cases, our speedup is almost quadratic in the “parallelism” the model can aﬀord, which may be the best possible. See the Baran, Demaine, Patrascu paper [here](http://erikdemaine.org/papers/3SUM_Algorithmica/paper.pdf).

Recently, a paper "Threesomes, Degenerates, and Love Triangles" by Grondlund and Pettie has proved that "the decision tree complexity of 3SUM is $O(n^{3/2}\sqrt{\log n})$, and that there is a randomized 3SUM algorithm running in $O(n^2(\log \log n)^2/\log n)$ time, and a deterministic algorithm running in $O(n^2(\log \log n)^{5/3}/(\log n)^{2/3})$ time.

These results refute the strongest version of the 3SUM conjecture, namely that its decision tree (and algorithmic) complexity is $Ω(n^2)$."

See this second paper [here](http://arxiv.org/abs/1404.0799).

Clearly, both are important papers. Not being an expert to this area, my question is about how to compare the impact and significance of either, given the different complexity models. Any other insightful comments about this problem is also welcome. For example had the first paper already ruled out the $\Omega(n^2)$ bound?

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


---

## 2 answers

### Answer by username_2 on 2014-04-05. Score: 14 | Accepted answer

Here are some points that help give perspective to the new results.

The decision tree complexity result is big. One line of attack (and Jeff Erickson can say more on this) was to try and lower bound 3SUM via looking at the decision complexity of the problem (i.e the number of comparisons needed to solve the problem). The hope was that something close to $\Omega(n^2)$ was attainable.

This result decisively trashes that argument with a $O(n^{3/2})$ bound. Note that this doesn't say anything about the true complexity of the problem. It says that a decision tree lower bound isn't going to happen. And that (along with other evidence) casts doubt on the basic premise that 3SUM is "morally" close to $n^2$.

The algorithmic result is subquadratic unconditionally (i.e not in a word-parallel model). That is a big deal, although I suppose one might quibble about the fact that it's not $O(n^{2-\epsilon})$ for some constant $\epsilon$.

As @username_1 says, this could very well be the beginning of a a series of new results. It's really hard to say. The current upper bound comes from "re-implementing" the decision tree algorithm with some magic tricks from Timothy Chan. It's conceivable that this could be pushed further.

> **Comments:**
> **username_3**: _Jeff Erickson can say more on this_ — Not much more to say, really. I proved that a natural decision tree model requires depth $\Omega(n^2)$; the new paper shows that with a very slighty stronger model, depth $O(n^{3/2})$ is enough. In retrosect, this result shouldn't be surprising, in light of Fredman's and Chan's results on sorting X+Y and shortest paths. But it does completely close off a natural line of attack. As I told Seth, I'm simultaneously incredibly relieved and incredibly jealous.  

---

### Answer by username_1 on 2014-04-05. Score: 14

The first paper essentially gives a subquadratic algorithm if we know that every input number has $w$ bits and we can add two $w$ bit numbers in one step. This was not a very surprising result and it did not rule out an $\Omega(n^2)$ bound.

The second paper does not use any such assumptions and improves the exponent of $n$ for decision trees, which is a surprise, although not as big as it would be for all algorithms, for which they have only improved slightly (thus disproving the strongest conjecture). I would guess that more results will follow shortly.

> **Comments:**
> **username_0**: I am happy with both answers, but could only accept one, so I accepted the more detailed one.  

---

