Comparing Two Algorithms for 3SUM problem over Integers

Question

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 afford, which may be the best possible. See the Baran, Demaine, Patrascu paper here.

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.

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?

Answer 1

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 @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.

Answer 2

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.