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 ${S}$ the problem is to determine if there are three elements ${x,y,z}$ in ${S}$,

$\displaystyle x + y + z = 0.$

Actually the version they work on allows ${S}$ 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.

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 ${O(n^{3/2}\sqrt{\log n})}$.

So this means that the 3SUM problem has a sub-quadratic algorithm. No. It means that it has decision tree complexity that is order ${n^{3/2}}$, 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:

$\dots$ we shall refer to the ingenious observation that ${a+b < c+d}$ if and only if ${a-c < d-b}$ 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 ${n}$ numbers whose sorted order is one of ${\Pi}$ permutations can be sorted with ${2n+\log \Pi}$ 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 ${n^{2}(\log n)}.$ Very neat.

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.

1. August 16, 2014 11:42 am

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…

2. August 16, 2014 11:44 am

ps any thoughts on the recent fields medals/ nevanlinna prize?

August 17, 2014 10:24 am

vznvzn

Yes we plan to comment on those

August 16, 2014 10:14 pm

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.

August 17, 2014 10:21 am

Craig

• August 17, 2014 1:22 pm

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.

August 18, 2014 7:47 pm

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.