Speaker: Omer Gold (TAU)

Title: On 3SUM and Related Problems

Abstract:
---------
The 3SUM problem is to decide, given a set of $n$ real numbers, whether any
three sum to zero.  It was widely conjectured that a trivial $O(n^2)$-time
algorithm is optimal and over the years the consequences of this conjecture
have been revealed, mainly in the context of obtaining conditional lower
bounds. This 3SUM conjecture implied $\Omega(n^2)$ lower bounds on numerous
problems in computational geometry, dynamic graph algorithms, and more.

We review a recent breakthrough by Allan Gronlund and Seth Pettie (FOCS
2014). In their paper, they refute this conjecture and also obtain a major
improvement in the understating of the decision tree complexity of some
foundational problems in *P*.

We will show:

(i) The decision tree complexity of the 3SUM problem is
$O(n^{3/2}\sqrt{\log n})$.

(ii) A deterministic subquadratic algorithm for the 3SUM which runs in
$O(n^2 / (\log n/\log\log n)^{2/3})$ time.

(iii) The decision tree complexity for finding zero-weight triangles in
weighted graphs (Zero Triangle problem) is $O(n^{5/2}\sqrt{\log n})$.

The techniques used are mainly borrowed from studies about the complexity
of the (min,+)-matrix-product, another foundational problem in P which is
widely known for its relation to the APSP (all pairs shortest paths)
problem. We will start by showing the techniques used for the
(min,+)-matrix-product by Michael Fredman (1976) and Timothy M. Chan
(2008), then we show how Gronlund and Pettie embraced them for obtaining
their results.

If time permits we will show how we employ some of these techniques to
study the decision tree complexity of the Discrete Frechet Distance in
various metrics.