Clustered integer 3SUM via additive combinatorics

Timothy M. Chan, Moshe Lewenstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Electronic)9781450335362
StatePublished - Jun 14 2015
Externally publishedYes
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
Country/TerritoryUnited States


  • 3SUM
  • Additive combinatorics
  • Convolution
  • Fast Fourier transform
  • Histogram indexing
  • Matrix multiplication

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Clustered integer 3SUM via additive combinatorics'. Together they form a unique fingerprint.

Cite this