Talk:3SUM

Subquadratic algorithms

I suggest citing this paper which obtains subquadratic algorithms for 3SUM when you can manipulate the bits in the input integers. I hesitate to add the citation myself because I am an author of the paper. —Erik Demaine 05:27, 13 February 2007 (UTC)

Now we need an update for http://arxiv.org/abs/1404.0799 Mglisse (talk) 08:15, 6 January 2015 (UTC)

Correctness of quadratic algorithm

The explanation of why the posted algorithm works seemingly contained some errors, which I hopefully managed to fix. What is still missing is some explanation of how this algorithm makes use of the sortedness of the array. As it stands, it doesn't really help the reader to understand what's going on much at all. Wppds (talk) 07:31, 7 April 2014 (UTC)

Subquadratic 3SUM

I think there is no need to mention the results of Baran, Demaine and Pătraşcu in the first paragraph as they are appropriate only for Integer3SUM. Also their significance is shadowed by the new result of Gronlund and Pettie.

Opening statment

The opening statment characterizes 3SUM as the problem of determining whether a subset of size three of a set of REALS sums zero, when the input set should be composed of integers.

The problem has been considered both for integers (represented in binary on a word RAM, where you can hash them and use them as indices into lookup tables and so on) and for numbers in a real model of computation where all you can do is add them and compare them. Saying that it is only for integers is too dogmatic, and misses important aspects of the problem. —David Eppstein (talk) 03:06, 3 February 2017 (UTC)