TY - GEN

T1 - Clustered integer 3SUM via additive combinatorics

AU - Chan, Timothy M.

AU - Lewenstein, Moshe

N1 - Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2015/6/14

Y1 - 2015/6/14

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

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

KW - 3SUM

KW - Additive combinatorics

KW - Convolution

KW - Fast Fourier transform

KW - Histogram indexing

KW - Matrix multiplication

UR - http://www.scopus.com/inward/record.url?scp=84958244101&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958244101&partnerID=8YFLogxK

U2 - 10.1145/2746539.2746568

DO - 10.1145/2746539.2746568

M3 - Conference contribution

AN - SCOPUS:84958244101

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 31

EP - 40

BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015

Y2 - 14 June 2015 through 17 June 2015

ER -