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

3SUMadditive combinatoricsconvolutionfast Fourier transformhistogram indexingmatrix multiplication

Mathematics Subject Classification ID

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

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

(54)

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

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)