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 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.