Mark Gritter (markgritter) wrote,
Mark Gritter

Sub-quadratic by a tiny, tiny bit

I was reading a post on the 3SUM problem, and a commenter pointed to a new result: "Threesomes, Degenerates, and Love Triangles" which produces a new bound that is just a tiny bit better than existing results.

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)).
  • Post a new comment


    default userpic

    Your reply will be screened

    Your IP address will be recorded