3SUM is Subquadratic

Speaker: Seth Pettie

Date: Tuesday, November 04, 2014

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: G449 (Patil/Kiva)

Event Type:

Room Description:

Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan, MIT, CSAIL

Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Relevant URL: http://toc.csail.mit.edu/node/602

Speaker URL: None

Speaker Photo:
None

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: Seth Petti, 3SUM is Subquadratic

Abstract:

The 3SUM problem is to decide, given a set of N real numbers, whether
any three of them sum to zero. A simple algorithm solves 3SUM in
O(N^2) time and it has long been conjectured that this is the best
possible.

The significance of the 3SUM problem does not lie with its practical
applications (roughly zero) but with the long list of problems in
computational geometry that are reducible from 3SUM. Some examples
include deciding whether a point set contains 3 colinear points,
calculating the area of the union of a set of triangles, and
determining whether one convex polygon can be placed within another
convex polygon. If 3SUM requires N^2 time then all 3SUM-hard problems
require N^2 time. More recently Patrascu gave many conditional lower
bounds on triangle enumeration and dynamic data structures that rely
on the hardness of 3SUM over the integers.

In this talk I'll present a non-uniform (decision-tree) algorithm for
3SUM that performs only N^{3/2} comparisons and a uniform 3SUM
algorithm running in O(N^2/polylog(N)) time. This result refutes the
3SUM conjecture and casts serious doubts on the optimality of many
O(N^2) geometric algorithms.

This is joint work with Allan Gronlund. A manuscript is available at
arXiv:1404.0799.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Colloquium - 2014.

Created by Deborah Goodwin Email at Tuesday, July 29, 2014 at 11:35 AM.