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

• Publication year

  2015

• Venue

  Symposium on the Theory of Computing

• Publication date

  2015-02-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/2746539.2746568arXiv 1502.05204
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Additive Combinatorics and its Applications in Theoretical Computer Science

  2017cited by this paper
• An O(n3log⁡log⁡n/log2⁡n) time algorithm for all pairs shortest paths

  2016cited by this paper
• New bounds in Balog-Szemerédi-Gowers theorem

  2015cited by this paper
• 3SUM Hardness in (Dynamic) Data Structures

  2014cited by this paper
• On Hardness of Jumbled Indexing

  2014cited by this paper
• Threesomes, Degenerates, and Love Triangles

  2014cited by this paper
• Consequences of Faster Alignment of Sequences

  2014cited by this paper
• 3SUM, 3XOR, Triangles

  2013cited by this paper
• Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet

  2013cited by this paper
• Faster all-pairs shortest paths via circuit complexity

  2013influential reference
• Multiplying matrices faster than coppersmith-winograd

  2012cited by this paper
• Sub-quadratic time and linear space data structures for permutation matching in binary strings

  2012cited by this paper
• Faster Algorithms for Rectangular Matrix Multiplication

  2012cited by this paper
• An O(n 3 loglogn/log2 n) Time Algorithm for All Pairs Shortest Paths

  2012cited by this paper
• On the possibility of faster SAT algorithms

  2010cited by this paper
• On Table Arrangements, Scrabble Freaks, and Jumbled Pattern Matching

  2010cited by this paper
• Towards polynomial lower bounds for dynamic problems

  2010cited by this paper
• Indexing permutations for binary strings

  2010cited by this paper
• Finding, minimizing, and counting weighted subgraphs

  2009influential reference
• Regularity Lemmas and Combinatorial Algorithms

  2009influential reference
• On a Certain Generalization of the Balog-Szemerédi-Gowers Theorem

  2008influential reference
• More algorithms for all-pairs shortest paths in weighted graphs

  2007cited by this paper
• Deterministic Length Reduction: Fast Convolution in Sparse Data and Applications

  2007cited by this paper
• Many additive quadruples

  2007cited by this paper
• Selected Results in Additive Combinatorics: An Exposition

  2007cited by this paper
• Foundations of a Structural Theory of Set Addition

  2007cited by this paper
• Additive Combinatorics: Long arithmetic progressions in sum sets

  2006cited by this paper
• Necklaces, Convolutions, and X+Y

  2006cited by this paper
• On a question of Erdős and Moser

  2005cited by this paper
• Subquadratic Algorithms for 3SUM

  2005cited by this paper
• Verifying candidate matches in sparse and wildcard matching

  2002influential reference
• A new proof of Szemerédi's theorem

  2001influential reference
• Exact and Approximate Distances in Graphs - A Survey

  2001cited by this paper
• A NEW PROOF OF SZEMER ´ EDI'S THEOREM

  2001cited by this paper
• Fast Rectangular Matrix Multiplication and Applications

  1998cited by this paper
• Pattern matching for spatial point sets

  1998cited by this paper
• On a Class of O(n2) Problems in Computational Geometry

  1995cited by this paper
• New Results and Open Problems Related to Non-Standard Stringology

  1995cited by this paper
• A statistical theorem of set addition

  1994influential reference
• Self-testing/correcting with applications to numerical problems

  1990cited by this paper

• Derandomizing Pseudopolynomial Algorithms for Subset Sum

  2026influential citation
• Preprocessed 3SUM for Unknown Universes with Subquadratic Space

  2026influential citation
• Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Linear Integer Arithmetic

  2025cites this paper
• Improved Time-Space Tradeoffs for 3SUM-Indexing

  2025cites this paper
• Weakly Approximating Knapsack in Subquadratic Time

  2025cites this paper
• All-Pairs Shortest Paths with Few Weights per Node

  2025cites this paper
• Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses

  2025cites this paper
• Discrete Effort Distribution via Regret-Enabled Greedy Algorithm

  2025cites this paper
• A pumping-like lemma for languages over infinite alphabets

  2025cites this paper
• k-SUM Hardness Implies Treewidth-SETH

  2025cites this paper
• Shaving Logs via Large Sieve Inequality: Faster Algorithms for Sparse Convolution and More

  2024cites this paper
• Approximating Partition in Near-Linear Time

  2024cites this paper
• An Improved Pseudopolynomial Time Algorithm for Subset Sum

  2024cites this paper
• Sumsets, 3SUM, Subset Sum: Now for Real!

  2024influential citation
• Beating Bellman's Algorithm for Subset Sum

  2024cites this paper
• Recognizing Sumsets is NP-Complete

  2024cites this paper
• 3SUM in Preprocessed Universes: Faster and Simpler

  2024influential citation
• Parameterized Algorithms on Integer Sets with Small Doubling: Integer Programming, Subset Sum and k-SUM

  2024cites this paper
• Even Faster Knapsack via Rectangular Monotone Min-Plus Convolution and Balancing

  2024cites this paper
• Convolution and Knapsack in Higher Dimensions

  2024cites this paper
• 0-1 Knapsack in Nearly Quadratic Time

  2023cites this paper
• Deterministic 3SUM-Hardness

  2023cites this paper
• Deterministic Sparse Pattern Matching via the Baur-Strassen Theorem

  2023influential citation
• The Time Complexity of Fully Sparse Matrix Multiplication

  2023cites this paper
• Improved Algorithms for Integer Complexity

  2023cites this paper
• Sparse Convolution for Approximate Sparse Instance

  2023cites this paper
• Structured (min,+)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(\min ,+)$$\end{document}-convolution and its applic

  2023cites this paper
• Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution

  2023cites this paper
• Space-Time Tradeoffs for Conjunctive Queries with Access Patterns

  2023cites this paper
• Fredman’s Trick Meets Dominance Product: Fine-Grained Complexity of Unweighted APSP, 3SUM Counting, and More

  2023influential citation
• Fast Convolutions for Near-Convex Sequences

  2023cites this paper
• Faster Algorithms for Text-to-Pattern Hamming Distances

  2023cites this paper
• Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

  2022cites this paper
• Faster min-plus product for monotone instances

  2022influential citation
• Approximate Circular Pattern Matching

  2022influential citation
• Gapped String Indexing in Subquadratic Space and Sublinear Query Time

  2022influential citation
• Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics

  2022influential citation
• Removing Additive Structure in 3SUM-Based Reductions

  2022influential citation
• Improved Bounds for Rectangular Monotone Min-Plus Product

  2022influential citation
• Structured (min, +)-Convolution And Its Applications For The Shortest Vector, Closest Vector, and Separable Nonlinear Knapsack Problems

  2022cites this paper
• Flip-swap languages in binary reflected Gray code order

  2022cites this paper
• Bisection of Bounded Treewidth Graphs by Convolutions

  2021cites this paper
• Space-Time Tradeoffs for Answering Boolean Conjunctive Queries

  2021cites this paper
• Hardness of Detecting Abelian and Additive Square Factors in Strings

  2021influential citation
• Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution

  2021cites this paper
• Fine-Grained Hardness for Edit Distance to a Fixed Sequence

  2021cites this paper
• A (probably) optimal algorithm for Bisection on bounded-treewidth graphs

  2021cites this paper
• Sparse nonnegative convolution is equivalent to dense nonnegative convolution

  2021cites this paper
• Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal

  2021cites this paper
• Inside the Binary Reflected Gray Code: Flip-Swap Languages in 2-Gray Code Order

  2021cites this paper
• Fast n-fold Boolean Convolution via Additive Combinatorics

  2021cites this paper
• General Space-Time Tradeoffs via Relational Queries

  2021cites this paper
• Binary Dynamic Time Warping in Linear Time

  2021cites this paper
• All non-trivial variants of 3-LDT are equivalent

  2020cites this paper
• Frontiers in Algorithmics: 14th International Workshop, FAW 2020, Haikou, China, October 19-21, 2020, Proceedings

  2020cites this paper
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance

  2020cites this paper
• Algorithms for Processing

  2020cites this paper
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word

  2020cites this paper
• An optimal algorithm for Bisection for bounded-treewidth graphs

  2020cites this paper
• On Δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Delta $$\end{document}-modular integer linear problems in the can

  2020cites this paper
• Equivalences between Non-trivial Variants of 3LDT and Conv3LDT

  2020cites this paper
• Language and Automata Theory and Applications: 14th International Conference, LATA 2020, Milan, Italy, March 4–6, 2020, Proceedings

  2020cites this paper
• Weighted Prefix Normal Words: Mind the Gap

  2020cites this paper
• On Near-Linear-Time Algorithms for Dense Subset Sum

  2020cites this paper
• A Fine-Grained Perspective on Approximating Subset Sum and Partition

  2020cites this paper
• On Weighted Prefix Normal Words

  2020cites this paper
• Top-𝑘-convolution and the quest for near-linear output-sensitive subset sum

  2020influential citation
• k-Abelian Pattern Matching: Revisited, Corrected, and Extended

  2019cites this paper
• Nearly Optimal Sparse Polynomial Multiplication

  2019cites this paper
• Smallest k-Enclosing Rectangle Revisited

  2019cites this paper
• Near-optimal Linear Decision Trees for k-SUM and Related Problems

  2019cites this paper
• On Collapsing Prefix Normal Words

  2019cites this paper
• F L ] 2 8 M ay 2 01 9 On Collapsing Prefix Normal Words

  2019cites this paper
• Faster Pseudopolynomial Time Algorithms for Subset Sum

  2019cites this paper
• 3SUM with Preprocessing: Algorithms, Lower Bounds and Cryptographic Applications

  2019influential citation
• D S ] 6 M ay 2 01 9 A Subquadratic Approximation Scheme for Partition

  2019cites this paper
• Massively Parallel Algorithms for String Matching with Wildcards

  2019cites this paper
• Data structures meet cryptography: 3SUM with preprocessing

  2019influential citation
• Approximating Subset Sum is equivalent to Min-Plus-Convolution

  2019cites this paper
• Sublinear-Time Sparse Recovery, and Its Power in the Design of Exact Algorithms

  2019cites this paper
• String Matching with Wildcards in the Massively Parallel Computation Model

  2019cites this paper
• Approximation Schemes for 0-1 Knapsack

  2018cites this paper
• On Integer Programming and Convolution

  2018cites this paper
• Algorithms above the noise floor

  2018cites this paper
• More Logarithmic-factor Speedups for 3SUM, (median,+)-convolution, and Some Geometric 3SUM-hard Problems

  2018cites this paper
• Forbidden Configurations in Discrete Geometry

  2018cites this paper
• Synergies between Adaptive Analysis of Algorithms, Parameterized Complexity, Compressed Data Structures and Compressed Indices (Dagstuhl Seminar 18281)

  2018cites this paper
• A Subquadratic Algorithm for 3XOR

  2018cites this paper
• N ov 2 01 8 On Integer Programming and Convolution ∗

  2018cites this paper
• On Infinite Prefix Normal Words

  2018cites this paper
• Fast algorithms for knapsack via convolution and prediction

  2018influential citation
• On Integer Programming, Discrepancy, and Convolution

  2018cites this paper
• A Subquadratic Approximation Scheme for Partition

  2018cites this paper
• D S ] 6 A pr 2 01 8 Subquadratic Approximation Scheme for Partition

  2018cites this paper
• Shortest Paths in Geometric Intersection Graphs

  2018cites this paper
• On Abelian Longest Common Factor with and without RLE

  2018influential citation
• A Nearly Quadratic Bound for Point-Location in Hyperplane Arrangements, in the Linear Decision Tree Model

  2018cites this paper
• Fast algorithms for Abelian periods in words and greatest common divisor queries

  2017cites this paper
• A Nearly Quadratic Bound for k-SUM , and Point-Location in Hyperplane Arrangements , in the Linear Decision Tree Model ∗

  2017cites this paper
• A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM

  2017cites this paper