(Min,+)-Convolutions, 3SUM and Additive Combinatorics

Title: "(Min,+)-Convolutions, 3SUM and Additive Combinatorics"
Speaker: Moshe Lewenstein, Bar-Ilan University
Time/Date: Thursday, Feb 18, 3-4 pm
Location: Room 5510

Abstract:
We present a collection of new results on problems related to 3SUM, including:

The first truly subquadratic algorithm for

1. computing the (min,+) convolution for monotone increasing sequences with 
   integer values bounded by $O(n)$,
2. solving 3SUM for monotone sets in 2D with integer coordinates bounded by 
   $O(n)$, and
3. preprocessing a binary string for histogram indexing (also called 
   jumbled indexing).

The running time is O(n^{1.859})$ with randomization, or $O(n^{1.864})$ 
deterministically.

This greatly improves the previous $n^2/2^{\Omega(\sqrt{\log n})}$ time 
bound obtained from Williams' recent result on all-pairs shortest paths 
[STOC'14], and answers an open question raised by several researchers 
studying the histogram indexing problem.

The first algorithm for histogram indexing for any constant alphabet size 
that achieves truly subquadratic preprocessing time and truly sublinear 
query time.

1. A truly subquadratic algorithm for integer 3SUM in the case when the 
   given set can be partitioned into $n^{1-\delta}$ clusters each covered 
   by an interval of length $n$, for any constant $\delta>0$.

2. An algorithm to preprocess any set of $n$ integers so that subsequently 
   3SUM on any given subset can be solved in $\OO(n^{13/7})$ time.

All these results are obtained by a surprising new technique, based on the
Balog--Szemer\'edi--Gowers Theorem from additive combinatorics.

Joint work with Timothy Chan

More information on the CSE Theory Seminars can be found at
http://cse.hkust.edu.hk/tcsc/seminars.html