Clustered Integer 3SUM via Additive Combinatorics

DOI10.1145/2746539.2746568MaRDI QIDQ2941486zbMATH OpenOpenAlexFDO

Authors Timothy M. Chan, Moshe Lewenstein

Publication date 21 August 2015

Published in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.05204

zbMATH Keywords

convolution3SUMfast Fourier transformmatrix multiplicationadditive combinatoricshistogram indexing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We present a collection of new results on problems related to 3SUM, including: 1. The first truly subquadratic algorithm for ${\displaystyle }$ 1a. computing the (min,+) convolution for monotone increasing sequences with integer values bounded by $O(n)$, ${\displaystyle }$1b. solving 3SUM for monotone sets in 2D with integer coordinates bounded by $O(n)$, and ${\displaystyle }$1c. preprocessing a binary string for histogram indexing (also called jumbled indexing). The running time is: $O(n^{(9+sqrt177)/12},extrmpolylog,n)=O(n^{1.859})$ with randomization, or $O(n^{1.864})$ deterministically. This greatly improves the previous $n^2/2^{Omega(sqrtlogn)}$ 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-delta}$ clusters each covered by an interval of length $n$, for any constant $delta>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},extrmpolylog,n)$ time. All these results are obtained by a surprising new technique, based on the Balog--Szemer'edi--Gowers Theorem from additive combinatorics.

Recommendations

• Three-term arithmetic progressions and sumsets
• A new triple sum combinatorial identity
• Algorithmic determination of the enumerator for sums of three triangular numbers
• Higher lower bounds from the 3SUM conjecture
• On binary Kloosterman sums divisible by 3
• Clusters of integers with equal total stopping times in the 3x+1 problem
• Sums of powers of integers divisible by three
• A combinatorial problem that arose in integer \(B_3\) sets
• Cubic congruences and sums involving 3k k
• On sums involving products of three binomial coefficients

Cites work

• Approximate distance oracles
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Fast C-K-R partitions of sparse graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On approximate distance labels and routing schemes with affine stretch
• On sparse spanners of weighted graphs
• Ramsey partitions and proximity data structures
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Shortest-path queries in static networks

Cited in

(52)

• How hard is it to find (honest) witnesses?
• More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems
• Fast convolutions for near-convex sequences
• Binary jumbled pattern matching: suffix tree indexing
• Weighted prefix normal words: mind the gap
• Bubble-flip -- a new generation algorithm for prefix normal words
• Approximate circular pattern matching
• Flip-swap languages in binary reflected Gray code order
• scientific article; zbMATH DE number 7525479 (Why is no real title available?)
• Smallest k-enclosing rectangle revisited
• Permuted scaled matching
• Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
• Smallest \(k\)-enclosing rectangle revisited
• On prefix normal words and prefix normal forms
• Extreme witnesses and their applications
• On integer programming and convolution
• On infinite prefix normal words
• Longest common substring with approximately \(k\) mismatches
• General space-time tradeoffs via relational queries
• Fast algorithms for abelian periods in words and greatest common divisor queries
• On Multidimensional and Monotone k-SUM
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• Structured ( ,+)-convolution and its applications for the shortest/closest vector and nonlinear knapsack problems
• Binary jumbled indexing: suffix tree histogram
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Fine-grained hardness for edit distance to a fixed sequence
• Current algorithms for detecting subgraphs of bounded treewidth are probably optimal
• Fast n-fold Boolean convolution via additive combinatorics
• The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance
• A polyhedral perspective on tropical convolutions
• Algorithms and Data Structures
• Subquadratic algorithms for 3SUM
• 3SUM in preprocessed universes: faster and simpler
• Bisection of bounded treewidth graphs by convolutions
• Even faster knapsack via rectangular monotone min-plus convolution and balancing
• Parameterized algorithms on integer sets with small doubling: integer programming, subset sum and k-SUM
• Extreme witnesses and their applications
• scientific article; zbMATH DE number 7122316 (Why is no real title available?)
• Discrete effort distribution via regret-enabled greedy algorithm
• On -modular integer linear problems in the canonical form and equivalent problems
• Improved bounds for rectangular monotone min-plus product and applications
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• Fredman's trick meets dominance product: fine-grained complexity of unweighted APSP, 3SUM counting, and more
• Removing additive structure in 3SUM-based reductions
• Stronger 3-SUM lower bounds for approximate distance oracles via additive combinatorics
• Gapped string indexing in subquadratic space and sublinear query time
• Deterministic 3SUM-hardness
• A subquadratic algorithm for 3XOR
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Hardness of RNA folding problem with four symbols
• Inside the binary reflected gray code: flip-swap languages in 2-gray code order
• Efficient indexes for jumbled pattern matching with constant-sized alphabet

Describes a project that uses

Uses Software

• Graphs

This page was built for publication: Clustered Integer 3SUM via Additive Combinatorics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941486)