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(nn(9+√177/12polylogn) = O(n1.859) with randomization, or O(n1.864)) deterministically. This greatly improves the previous n2/Ω(√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 n1-δ 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(n13/7 polylogn) time. All these results are obtained by a surprising new technique, based on the Balog-Szemerédi-Gowers Theorem from additive combinatorics.