A puzzle courtesy of Mohan Paturi:
Given a set S of n numbers, the 3SUM problem asks whether there exist a,b,c ∈ S such that a+b+c=0. It is generally believed that this should take around n2 time.
But let's assume |S+S| = t ≪ n2. Show that the problem can be solved in O(t lg2n) time.
Any ideas for a better bound?