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.
Let’s start by recalling the definition of 3SUM. Given a set of integers the problem is to determine if there are three elements in ,
Actually the version they work on allows to be a set of real numbers, not just integers. This is important because there could be tricks that work with integers—taking mods for example—that cannot be made to work with reals. Since they are getting upper bounds this generalization is just fine.
They prove a variety of theorems in their paper, so look at it for all the details. One of the main results is:
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 , dropping the logarithmic factor. So let’s look quickly at what this really means, and at the same time give some idea of how they prove such a result.
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 Very neat.
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]