Talk:3SUM

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Start Class
Low Priority
 Field: Discrete mathematics

Subquadratic algorithms[edit]

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[edit]

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[edit]

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.