(Min,+)-Convolutions, 3SUM and Additive Combinatorics – University of Copenhagen

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

EADS talk by Moshe Lewenstein

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

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édi-Gowers Theorem from additive 
combinatorics.

Joint work with Timothy Chan

About the speaker 
Moshe Lewenstein has been a Professor in the Computer Science Department at Bar Ilan University, Israel, since late 2002.

Moshe Lewenstein's research interests include analysis of algorithms with a special emphasis on Pattern Matching, Data Structures and Text Indexing.