Source-linked AI summary
Clustered Integer 3SUM via Additive Combinatorics
Timothy M. Chan, Moshe Lewenstein
TL;DR
The paper targets unresolved subquadratic algorithms for structured convolution and 3SUM-related problems. It uses the Balog–Szemerédi–Gowers Theorem to obtain faster algorithms, including a randomized eO(n^1.859) bound for bounded monotone convolution and related applications.
Problem
Truly subquadratic algorithms remained open for bounded monotone (min,+) convolution and related structured 3SUM+ problems.
Method
The paper applies the Balog–Szemerédi–Gowers Theorem through a reformulation of bounded monotone convolution as 3SUM+ on monotone point sets.
Results
The randomized algorithm achieves eO(n^1.859) expected time for bounded monotone convolution and yields related subquadratic results for histogram indexing, clustered 3SUM+, and preprocessed integer universes.
Takeaways & Limitations
The technique extends subquadratic algorithms beyond the original convolution problem to constant-alphabet histogram indexing and several structured or preprocessed 3SUM+ settings.
Takeaways & Limitations
The deterministic bound is subquadratic only for dimensions d≤7 under the current matrix-multiplication exponents.
Abstract
from arXiv · showhide
We present a collection of new results on problems related to 3SUM, including: 1. The first truly subquadratic algorithm for $\ \ \ \ \ $ 1a. computing the (min,+) convolution for monotone increasing sequences with integer values bounded by $O(n)$, $\ \ \ \ \ $1b. solving 3SUM for monotone sets in 2D with integer coordinates bounded by $O(n)$, and $\ \ \ \ \ $1c. preprocessing a binary string for histogram indexing (also called jumbled indexing). The running time is: $O(n^{(9+\sqrt{177})/12}\,\textrm{polylog}\,n)=O(n^{1.859})$ with randomization, or $O(n^{1.864})$ deterministically. This greatly improves the previous $n^2/2^{Ω(\sqrt{\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. 2. The first algorithm for histogram indexing for any constant alphabet size that achieves truly subquadratic preprocessing time and truly sublinear query time. 3. A truly subquadratic algorithm for integer 3SUM in the case when the given set can be partitioned into $n^{1-δ}$ clusters each covered by an interval of length $n$, for any constant $δ>0$. 4. 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}\,\textrm{polylog}\,n)$ time. All these results are obtained by a surprising new technique, based on the Balog--Szemerédi--Gowers Theorem from additive combinatorics.
1 Introduction
The paper addresses longstanding subquadratic challenges in bounded monotone convolution, 3SUM+, APSP-related problems, and histogram indexing. It introduces additive-combinatorial techniques yielding faster algorithms across monotone, clustered, online-query, and preprocessed-universe settings.
- 1.1 Motivation: Bounded Monotone (min,+) Convolution: Bounded monotone convolution is a basic open special case connected to truly subcubic APSP and truly subquadratic 3SUM+.The problem uses monotone increasing sequences with integer values bounded by O(n).
- 1.3 New Technique via Additive Combinatorics: The technique reformulates bounded monotone convolution as 3SUM+ on two-dimensional monotone point sets and applies the Balog–Szemerédi–Gowers Theorem.The BSG construction’s algorithmic time complexity and polynomial parameter dependence are important for obtaining subquadratic bounds.
- 1.2 New Result: The first truly subquadratic bounded monotone (min,+) convolution algorithm runs in eO(n^1.859) expected time and supports related applications.The deterministic version is also truly subquadratic, and the approach relies on additive combinatorics.
- 1.4 Other Consequences of the New Technique: Integer 3SUM+ becomes truly subquadratic for clustered inputs, including when one set is covered by n^(1−δ) intervals of length n.The paper describes this as its most general known truly subquadratic setting for 3SUM.
- 1.4 Other Consequences of the New Technique: For any constant alphabet size d, histogram indexing receives truly subquadratic preprocessing and truly sublinear query time.The stated preprocessing is eO(n^(2−δ)) expected, with query time eO(n^(2/3+δ(d+13)/6)) for sufficiently small δ>0.
- 1.4 Other Consequences of the New Technique: Preprocessing integer universes enables subsequent 3SUM+ on arbitrary subsets in truly subquadratic eO(n^13/7) time.The result applies to general integer sets after preprocessing universes A0, B0, and S0.
2 Ingredients: The BSG Theorem/Corollary and FFT Lemma
The paper uses the Balog–Szemerédi–Gowers framework to decompose relevant pairs into structured subsets and a remainder, then computes small sumsets efficiently with FFT.
- BSG Theorem and Corollary: The BSG Theorem extracts structured subsets from many pairs whose sums occupy a small set, while the iterative corollary covers the remaining relevant pairs.The corollary repeatedly removes Cartesian products of extracted subsets and leaves a remainder set.
- BSG Theorem and Corollary: The BSG Corollary is crucial because its general graph formulation supports iterative removal of already covered pairs.This is the form needed when applications must cover all pairs with sums in S.
- Algorithmic construction: The BSG decomposition can be constructed in randomized near-quadratic expected time or deterministic matrix-multiplication time.The deterministic bound is O((1/α)^0.4651 N^2.3729), while the randomized construction is eO(N^2) expected time, with an additional alternative bound involving (1/α)^5|A|.
- FFT Lemma: The FFT Lemma computes a small sumset A + B efficiently when a linear-size superset T is known.It gives randomized expected eO(N) time and deterministic eO(N) time after eO(N^(1+ε)) preprocessing of T.
- FFT Lemma: The paper supplies self-contained FFT Lemma proofs and reduces the deterministic preprocessing cost to eO(N^(1+ε)).The randomized proof uses the fact that the superset T is available in the applications.
3 3SUM+ for Monotone Sets in [n]d
The main algorithm applies the BSG decomposition to grid cells of monotone sets, recursively handles uncovered cell pairs, and uses FFT on structured groups to obtain subquadratic 3SUM+ algorithms.
- The main algorithm: The algorithm partitions the universe into grid cells, aligns inputs so cell(a + b) = cell(a) + cell(b), and applies the BSG Corollary to cell representatives.Alignment costs only constant-factor overhead after decomposing each set into translated aligned subsets.
- The main algorithm: Uncovered cell pairs generate recursive calls on translated copies of [ℓ]^d, while structured BSG groups are processed with the FFT Lemma.The remainder creates O(α(n/ℓ)^2) recursive calls, and each structured group is filtered against S after sumset generation.
- The main algorithm: Choosing ℓ = n^0.0707 and 1/α = n^0.1313 for d = 2 yields O(n^1.859) expected time.The running-time recurrence balances grid-cell processing, recursive subproblems, and FFT-based structured cases.
- Limitations: The deterministic bound is subquadratic only for d ≤ 7 under current matrix-multiplication exponents.The randomized exponent approaches 2 as d grows, while a hypothetical ω = 2 would make the deterministic bound subquadratic for all d.
- 2D connected monotone case: For connected monotone sets in 2D, the sumset forms a region bounded by monotone curves, whose boundaries can be computed in O(n^1.859) expected time.Each vertical slice is an interval, and its lower endpoint can be found through simultaneous binary search using 3SUM+ queries.
- Applications: The same bound computes bounded monotone (min,+) convolution and supports binary histogram indexing with O(1) queries after O(n)-space preprocessing.The convolution reduction encodes sequences as connected monotone sets, while histogram indexing reduces to the convolution problem.
4 Generalization to Clustered Sets
The section replaces monotonicity with clusterability and derives subquadratic 3SUM+ algorithms for clustered sets, including monotone sets and histogram indexing.
- Clustered sets: Clusterability, rather than monotonicity, is the sole structural property required by the main algorithm.A set is (K,L)-clustered when covered by K disjoint hypercubes of volume L.
- Clustered sets: eO(K_AK_B + n^(12/7)(K_AL)^(1/7)) expected time solves 3SUM+ when A and B are clustered.The bound follows from the clustered-set corollary and does not require clusterability of S or per-cluster point bounds.
- Clustered sets: n^(2−Ω(δ)) expected time solves 3SUM+ when only A is (n^(1−δ), n)-clustered.This is presented as the most general setting in which the paper obtains a truly subquadratic algorithm.
- Monotone sets: For monotone sets in [n]^d, 3SUM+ runs in eO(n^(2−2/(d+13))) when A and B are monotone, or eO(n^(2−1/(d+6))) when only A is monotone.The bounds arise by viewing monotone sets as clustered at an appropriate grid scale.
- Applications: eO(n^(2−2/(d+13))) expected time answers all offline histogram queries for constant alphabet size d.The reduction uses prefix character-count vectors and their differences to represent substring histograms.
5 Online Queries
The section extends the clustered-set method to online membership queries in A+B, using preprocessing that separates low- and high-popularity cells.
- Main algorithm: The preprocessing/query tradeoff stores high-popularity sums explicitly while searching low-popularity buckets directly.Popularity is the number of cell pairs mapping to a sum cell; high-popularity cells are handled through the BSG decomposition.
- Tradeoffs: For clustered A and B, preprocessing takes eO(K_AK_B + n^(12/7)(K_AL)^(1/7)Q^(3/7)) time, uses eO(K_AK_B + K_ALQ) space, and answers queries in eO(n/Q).The parameter Q controls the preprocessing, space, and query-time tradeoff.
- Online 3SUM+: eO(n^(2−δ)) expected preprocessing supports monotone-set queries in eO(n^(2/3+δ(d+13)/6)) time.With only A monotone, the query time becomes eO(n^(2/3+δ(d+6)/3)).
- Online 3SUM+: eO(n^(2−2/(d+19))) preprocessing and eO(n^(1−2/(d+19))) query time balance preprocessing against n queries when A and B are monotone.These bounds are stated as slightly worse than the offline setting.
6 3SUM+ in Preprocessed Universes
The section shows that preprocessing integer universes enables subquadratic 3SUM on arbitrary subsets, with related graph and clusterability applications.
- Preprocessed universes: eO(n^(13/7)) time solves 3SUM+ on arbitrary subsets of three preprocessed integer universes after eO(n^2) expected preprocessing.The data structure uses O(n^(13/7)) space.
- Preprocessed universes: When the universe for S is not preprocessed, arbitrary subsets A and B still support 3SUM+ in eO(n^(19/10)) time after eO(n^2) expected preprocessing.This variant uses O(n^2) space.
- Main algorithm: The preprocessing partitions popular sums using the BSG Corollary and stores structured sumsets, while queries handle low-popularity sums by bucket scans.The total expected query time is balanced by setting t = 1/α = n^(1/10).
- Graph application: The framework yields an eO(n^2.9)-time algorithm for detecting a vertex-weighted K_1,3 with prescribed total weight.It preprocesses vertex weights and solves one 3SUM instance for each graph vertex.
- Scope: The K_1,3 application is explicitly described as contrived, while demonstrating potential usefulness of 3SUM on preprocessed universes.The paper contrasts it with a more general counting result whose bound is not subcubic for four-vertex subgraphs.
7 Proof and Time Complexity of the BSG Theorem/Corollary
The section analyzes the BSG construction algorithmically, obtaining randomized near-linear-in-input construction for the graph lemma and the time bounds used throughout the applications.
- Correctness: The constructed subsets A′ and B′ contain many length-3 paths between every pair, yielding the structural condition needed by the BSG theorem.The proof counts Ω(α^5|A||B|) paths using common-neighbor structure.
- Running time: The BSG construction terminates after eO(1/α) iterations with high probability, and the randomized estimates preserve correctness after O(δ) constant-factor adjustments.Sampling-based estimates are supported by Chernoff bounds.
- Deterministic construction: The deterministic Graph Lemma implementation uses rectangular matrix multiplication, with time O(M(|A|,|A|,|B|)).Matrix products compute the common-neighbor counts needed to identify bad pairs.
- Graph Lemma: The randomized Graph Lemma algorithm runs in eO((1/α)^5|A′| + (1/α)|B| + (1/α)^6) time and is correct with high probability.It estimates degrees and codegrees through random sampling rather than constructing the full auxiliary graph.
- BSG Corollary: The BSG Corollary obtains a deterministic bound of O((1/α)^0.4651N^2.3729) under the stated rectangular-multiplication bounds.This is the time bound used for deterministic versions of later applications.
8 Proof of the FFT Lemma
The FFT Lemma computes sumsets by hashing into a smaller universe with pseudo-additive functions, then applying FFT. Randomized and deterministic constructions provide the required hash families with near-linear running times, while later applications reuse the same framework.
- FFT Lemma: Pseudo-additive hashing reduces sumset computation to FFT over a smaller universe while preserving sums through an associated function.The reduction uses h and an associated h-hat satisfying h-hat(h(a)+h(b)) = h(a+b).
- FFT Lemma: A pseudo-perfect family needs only one collision-free hash function per target element, rather than a single perfect hash function for all elements.For each x in T, some h in H must have no collisions with x.
- Randomized construction: Randomly chosen modular hash functions yield a pseudo-perfect family with k = log N + 1 functions and constant overall failure probability.Each element avoids collisions under at least one function with high probability, by bounding prime divisors of pairwise differences.
- Deterministic construction: A deterministic multi-prime construction avoids brute-forcing all large primes and achieves eO(N^(1+ε)) time for any constant ε > 0.The construction selects smaller primes in separate rounds and repeatedly removes elements that remain collision-free under none of the resulting hash functions.
- Applications: The deterministic method improves sparse wildcard matching preprocessing to eO(N^(1+ε)), yielding the first quasi-linear-time deterministic algorithm for that problem.The application uses the text’s nonzero locations as the target set T.
9 Final Remarks
The paper establishes truly subquadratic algorithms for several 3SUM-related problems and identifies additive-combinatorial questions that could improve their exponents. It also formulates a biclique-cover problem whose combinatorial bounds directly affect an algorithmic application.
- Contributions: The paper’s main contribution is the first truly subquadratic algorithms for a variety of problems related to 3SUM, breaking the previous barrier.The authors note that the exponents could still be improved.
- Future directions: Reducing the α-dependency in the Balog–Szemerédi–Gowers Theorem is identified as a direction that could improve the paper’s results.An announced improvement may not apply because its extension with G is essential to these applications.
- Open problems: The paper asks for worst-case bounds on covering additive triples by bicliques while minimizing the sum of the sizes of their sumsets.The formulation uses subsets A, B, S of an abelian group of size N.
- Open problems: The Balog–Szemerédi–Gowers Corollary gives an O(N^13/7) bound for this biclique-cover cost, and improving it would affect at least one algorithmic application.The stated bound combines singleton bicliques with the corollary and optimizes α.
- Future directions: The authors propose studying additive-combinatorial extensions for larger-k SUM and monotone or bounded-difference (min,+) matrix multiplication.These are presented as directions extending the paper’s techniques and problem settings.