The 3SUM Assumption Is Wrong?
A new result on our three body problem
Allan Grønlund and Seth Pettie are leaders in algorithm design and related problems.
Today I want to give a quick follow up on our discussion of 3SUM based on a recent paper of theirs.
I had planned to report on the accepted papers that will soon appear at this upcoming 2014 FOCS conference. See here for all conference details. But Pettie just sent me their joint paper that almost answers the questions raised in the last discussion on “our three body problem.” The paper is called: Threesomes, Degenerates, and Love Triangles: I have no comment on this title. Wait saying “I have no comment” is really making a comment—oh well.
3SUM
Let’s start by recalling the definition of 3SUM. Given a set of integers 
Actually the version they work on allows
New Result
They prove a variety of theorems in their paper, so look at it for all the details. One of the main results is:
Theorem:
The decision tree complexity of 3SUM is.
So this means that the 3SUM problem has a sub-quadratic algorithm. No. It means that it has decision tree complexity that is order 
Decision Tree Complexity
Decision tree complexity is based on a simple model: a tree is defined that at each node makes a binary decision based on some test of the inputs. Various tests are allowed but here they are always linear in the inputs. This model has been studied for ages and many interesting results are known.
Some of the most exciting ones are based on insights of Michael Fredman. In particular he showed in 1976 several cool results about the power of decision trees. I should report in more detail on these ideas, since they are old but as the new 3SUM results show, still extremely powerful. One idea is used repeatedly in this paper:
we shall refer to the ingenious observation that
if and only if
as Fredman’s Trick.
Michael also proved an amazing result, in my opinion, that is also used in the current paper.
Lemma: A list of
numbers whose sorted order is one of
permutations can be sorted with
pairwise comparisons.
Here is their algorithm for 3SUM:
In their paper they prove the key facts: the algorithm is correct, and it can be implemented using Fredman’s and other ideas to have the claimed number of comparisons. What is also interesting is that such decision-tree type algorithms sometimes “cheat” by using the existence of the decision tree, but the cost of computing what the next comparison is can be very hard. This happens, for example, with the Knapsack Problem—see here. In their algorithm the cost of deciding the comparisons is order 
Open Problems
Allan Grønlund and Pettie’s beautiful result on 3SUM is evidence that there should be an actual algorithm. I remain optimistic, as always. Perhaps they will be able to prove that soon. In any case, the result is still wonderful.
[added link to paper]
so are you saying that maybe the cost of comparisons is high and why the decision tree cant immediately be turned into a general algorithm, because “decisions” at each node, ie comparisons, might be expensive? some sketch of that gap would be helpful…
ps any thoughts on the recent fields medals/ nevanlinna prize?
vznvzn
Yes we plan to comment on those
Reading the paper “Threesomes, Degenerates, and Love Triangles” on arxiv.org, I am not convinced that the algorithm described in section 5.1 runs in o(n^2) time. In this section, it claims that the total running-time for dominance reporting is O((n/g)^2), because this is the total size of the outputs. However, this is only the number of outputs, not the size. The size of each dominating pair that is output is the order of g^2. Hence, the total size of the outputs should be O(n^2), not O((n/g)^2). So this algorithm runs in O(n^2) time, not o(n^2) time.
Of course, I could be misunderstanding something.
Craig
Let me think about that
The output of the dominance reporting is a set of pairs of the form “(i,j)” indicating that point #i dominates point #j. Note that each pair has size O(1) (i and j are just log(n/g)-bit identifiers) independent of the dimension of the point set. I.e., point #i is in R^d but you don’t list all d coordinates in the output.
When I commented on the other thread, saying that it is impossible to solve 3-sum in o(n^2) time, I should have specified that I meant in a Turing machine model of computation. The algorithm by Pettie and Grønlund seems to work in a RAM model of computation.
Serious paper about the P versus NP Problem
http://hal.archives-ouvertes.fr/hal-00984866
Dr. Lipton, please elaborate what you mean by “an actual algorithm” when you said, “Allan Grønlund and Pettie’s beautiful result on 3SUM is evidence that there should be an actual algorithm.” Do you mean an actual algorithm that decides 3SUM with worst-case runtime that is subquadratic in the length of the input?