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).

Authors

• Timothy M. Chan
• Moshe Lewenstein

Keywords

• 3SUM
• additive combinatorics
• convolution
• fast fourier transform
• histogram indexing
• matrix multiplication