Clustered integer 3SUM via additive combinatorics

We present a collection of new results on problems related to 3SUM, including: • The first truly subquadratic algorithm for - computing the (min,+) convolution for monotone increasing sequences with integer values bounded by O(n), - solving 3SUM for monotone sets in 2D with integer coordinates bounded by O(n), and - preprocessing a binary string for histogram indexing (also called jumbled indexing). The running time is O(n^{n(9+√177/12}polylogn) = O(n^1.859) with randomization, or O(n^1.864)) deterministically. This greatly improves the previous n²/^Ω(√logn) 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. • A truly subquadratic algorithm for integer 3SUM in the case when the given set can be partitioned into n^1-δ clusters each covered by an interval of length n, for any constant δ > 0. • An algorithm to preprocess any set of n integers so that subsequently 3SUM on any given subset can be solved in O(n^13/7 polylogn) time. All these results are obtained by a surprising new technique, based on the Balog-Szemerédi-Gowers Theorem from additive combinatorics.