Clustered Integer 3SUM via Additive Combinatorics

被引:65
作者
Chan, Timothy M. [1 ]
Lewenstein, Moshe [2 ]
机构
[1] Univ Waterloo, Cheriton Sch Comp Sci, Waterloo, ON, Canada
[2] Bar Ilan Univ, Dept Comp Sci, Ramat Gan, Israel
来源
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2015年
基金
加拿大自然科学与工程研究理事会;
关键词
3SUM; convolution; additive combinatorics; histogram indexing; fast Fourier transform; matrix multiplication; ALGORITHMS;
D O I
10.1145/2746539.2746568
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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((9+root 177)/12) polylogn) = O(n(1.859)) with randomization, or O(n(1.864)) deterministically. This greatly improves the previous n(2)/2(Omega()root(log n)) 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-delta) clusters each covered by an interval of length n, for any constant delta > 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-Szemeredi-Gowers Theorem from additive combinatorics.
引用
收藏
页码:31 / 40
页数:10
相关论文
共 32 条
[1]  
Abboud A, 2014, LECT NOTES COMPUT SC, V8572, P39
[2]  
Amir A, 2014, LECT NOTES COMPUT SC, V8572, P114
[3]  
Amir A, 2007, LECT NOTES COMPUT SC, V4580, P183
[4]  
[Anonymous], ADDITIVE COMBINATORI
[5]   A STATISTICAL THEOREM OF SET ADDITION [J].
BALOG, A ;
SZEMEREDI, E .
COMBINATORICA, 1994, 14 (03) :263-268
[6]  
Balog A, 2007, CRM PROC & LECT NOTE, V43, P39
[7]  
Bansal Nikhil, 2012, Theory Comput., V8, P69, DOI [DOI 10.4086/TOC.2012.V008A004, 10.4086/TOC, DOI 10.4086/TOC]
[8]   Subquadratic algorithms for 3SUM [J].
Baran, Ilya ;
Demaine, Erik D. ;
Patrascu, Mihai .
ALGORITHMICA, 2008, 50 (04) :584-596
[9]   SELF-TESTING CORRECTING WITH APPLICATIONS TO NUMERICAL PROBLEMS [J].
BLUM, M ;
LUBY, M ;
RUBINFELD, R .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1993, 47 (03) :549-595
[10]   ON A CERTAIN GENERALIZATION OF THE BALOG-SZEMEREDI-GOWERS THEOREM [J].
Borenstein, Evan ;
Croot, Ernie .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) :685-694