The 3SUM problem is: given a set of numbers, does there exist a triple a,b,c such that a+b+c = 0? For real numbers, the best existing algorithm is O(N^2) and a lot of conditional bounds on other problems can be derived from the assumption that that's the best possible.

The new paper introduces an algorithm that is O(N^2 / (log N / log log N)^(2/3) ).

How much better is that? Well, at N=1000000, the numerator on that fraction is just 2.773. To get to a factor of 10, you need N to be about 10^75. In other words, for all practical purposes, the algorithm is useless--- rather than trying to get it right, you're better off tuning your implementation of the simple algorithm. But it's a potentially interesting advance because they also showed a better decision-tree bound than previously known, and got "subquadratic", but unfortunately not O(N^(2-e)).

## Error

Your reply will be screened

Your IP address will be recorded