Timothy M. Chan
ABSTRACT
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+√177)/12, polylog,n)=O(n1.859) with randomization, or O(n1.864) deterministically. This greatly improves the previous n2/2Ω(√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 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, polylog,n) time.
All these results are obtained by a surprising new technique, based on the Balog--Szemeredi--Gowers Theorem from additive combinatorics.
- Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Part I, pages 39--51, 2014.Google Scholar
Cross Ref
- Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP), Part I, pages 114--125, 2014.Google ScholarCross Ref
- Amihood Amir, Oren Kapah, and Ely Porat. Deterministic length reduction: Fast convolution in sparse data and applications. In Proceedings of the 18th Annual Symposium on Combinatorial Pattern Matching (CPM), pages 183--194, 2007. Google ScholarDigital Library
- Antal Balog. Many additive quadruples. In Additive Combinatorics, volume 43 of CRM Proc. Lecture Notes, page 39--49. Amer. Math. Soc., 2007.Google ScholarCross Ref
- Antal Balog and Endre Szemerédi. A statistical theorem of set addition. Combinatorica, 14:263--268, 1994.Google ScholarCross Ref
- Nikhil Bansal and Ryan Williams. Regularity lemmas and combinatorial algorithms. Theory of Computing, 8(1):69--94, 2012.Google ScholarCross Ref
- Ilya Baran, Erik D. Demaine, and Mihai Patraşcu. Subquadratic algorithms for 3SUM. Algorithmica, 50(4):584--596, 2008. Google ScholarDigital Library
- Manuel Blum, Michael Luby, and Ronitt Rubinfeld. Self-testing/correcting with applications to numerical problems. J. Comput. Syst. Sci., 47(3):549--595, 1993. Google ScholarDigital Library
- Evan Borenstein and Ernie Croot. On a certain generalization of the Balog--Szemerédi-Gowers theorem. SIAM J. Discrete Math., 25(2):685--694, 2011.Google ScholarCross Ref
- David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patraşcu, and Perouz Taslakian. Necklaces, convolutions, and X+Y. Algorithmica, 69(2):294--314, 2014.Google ScholarCross Ref
- Peter Burcsi, Ferdinando Cicalese, Gabriele Fici, and Zsuzsanna Lipták. On table arrangements, scrabble freaks, and jumbled pattern matching. In Proceedings of the 5th International Conference on Fun with Algorithms (FUN), pages 89--101, 2010. Google ScholarDigital Library
- Timothy M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. SIAM J. Comput., 39(5):2075--2089, 2010. Google ScholarDigital Library
- Richard Cole and Ramesh Hariharan. Verifying candidate matches in sparse and wildcard matching. In Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pages 592--601, 2002. Google ScholarDigital Library
- G. Freiman. Foundations of a structural theory of set addition. American Mathematical Society, Translations of Mathematical Monographs, 37, 1973.Google Scholar
- Anka Gajentaan and Mark H. Overmars. On a class of O(n^2) problems in computational geometry. Comput. Geom., 5:165--185, 1995. Google ScholarDigital Library
- William Timothy Gowers. A new proof of Szemerédi's theorem. Geom. Funct. Anal., 11:465--588, 2001.Google ScholarCross Ref
- Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. In Proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2014. Google ScholarDigital Library
- Yijie Han and Tadao Takaoka. An O(n^3 log log n/log^2 n) time algorithm for all pairs shortest paths. In Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), pages 131--141, 2012. Google ScholarDigital Library
- Zahra Jafargholi and Emanuele Viola. 3SUM, 3XOR, triangles. Electronic Colloquium on Computational Complexity (ECCC), 20:9, 2013.Google Scholar
- Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter. Efficient indexes for jumbled pattern matching with constant-sized alphabet. In Proceedings of the 21st Annual European Symposium on Algorithms (ESA), pages 625--636, 2013.Google ScholarCross Ref
- Tsvi Kopelowitz, Seth Pettie, and Ely Porat. 3SUM hardness in (dynamic) data structures. CoRR, abs/1407.6756, 2014.Google Scholar
- Shachar Lovett. Additive combinatorics and its applications in theoretical computer science (draft). 2013.Google Scholar
- Tanaeem M. Moosa and M. Sohel Rahman. Indexing permutations for binary strings. Inf. Process. Lett., 110(18--19):795--798, 2010. Google ScholarDigital Library
- Tanaeem M. Moosa and M. Sohel Rahman. Sub-quadratic time and linear space data structures for permutation matching in binary strings. J. Discrete Algorithms, 10:5--9, 2012. Google ScholarDigital Library
- Mihai Patraşcu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd Annual ACM Symposium on Theory of Computing (STOC), pages 603--610, 2010. Google ScholarDigital Library
- Mihai Patraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In Proceedings of the 21st Annual ACM--SIAM Symposium on Discrete Algorithms (SODA), pages 1065--1075, 2010. Google ScholarDigital Library
- Tomasz Schoen. New bounds in Balog--Szemerédi-Gowers Theorem, 2014. Combinatorica, to appear.Google Scholar
- Benny Sudakov, Endre Szemerédi, and Van Vu. On a question of Erdös and Moser. Duke Math. J., 129:129--155, 2005.Google ScholarCross Ref
- Terence Tao and Van Vu. Additive Combinatorics. Cambridge University Press, 2006.Google Scholar
- Virginia Vassilevska and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 455--464, 2009. Google ScholarDigital Library
- Emanuele Viola. Selected results in additive combinatorics: An exposition. In Theory of Computing Library, Graduate Surveys series, volume 3, pages 1--15. 2011.Google Scholar
- Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pages 664--673, 2014. Google ScholarDigital Library
- Uri Zwick. Exact and approximate distances in graphs--A survey. In Proceedings of the 9th Annual European Symposium on Algorithms (ESA), pages 33--48, 2001. Google ScholarDigital Library
Index Terms
- Clustered Integer 3SUM via Additive Combinatorics
Recommendations
Threesomes, Degenerates, and Love Triangles
Distributed Computing, Cryptography, Distributed Computing, Cryptography, Coding Theory, Automata Theory, Complexity Theory, Programming Languages, Algorithms, Invited Paper Foreword and DatabasesThe 3SUM problem is to decide, given a set of n real numbers, whether any three sum to zero. It is widely conjectured that a trivial O(n2)-time algorithm is optimal on the Real RAM, and optimal even in the nonuniform linear decision tree model. Over the ...
Improved Subquadratic 3SUM
In the 3SUM problem we are given three lists $$\mathcal {A}$$A, $$\mathcal {B}$$B, $$\mathcal {C}$$C, of n real numbers, and are asked to find $$(a,b,c)\in \mathcal {A}\times \mathcal {B}\times \mathcal {C}$$(a,b,c)źA B C such that $$a+b=c$$a+b=c. The ...
Subquadratic Algorithms for 3SUM
We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of $O(n^{2}/\max\{\frac{w}{\lg^{2}w},\frac{\lg^{2}n}{(\lg\lg n)^{2}}\})$ . In the circuit RAM with ...
Comments