Improved bounds for 3SUM, k-SUM, and linear degeneracy

DOI10.4230/LIPICS.ESA.2017.42MaRDI QIDQ5111730zbMATH OpenOpenAlexFDO

Authors Omer Gold, Micha Sharir

Publication date 27 May 2020

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

zbMATH Keywords

3SUM\(k\)-SUMfractional cascadinglinear decision treeslinear degeneracy

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Abstract: Given a set of $n$ real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Gr{o}nlund and Pettie [FOCS'14], a simple $Theta(n^2)$-time deterministic algorithm for this problem was conjectured to be optimal. Over the years many algorithmic problems have been shown to be reducible from the 3SUM problem or its variants, including the more generalized forms of the problem, such as $k$-SUM and $k$-variate linear degeneracy testing ($k$-LDT). The conjectured hardness of these problems have become extremely popular for basing conditional lower bounds for numerous algorithmic problems in P. In this paper, we show that the randomized $4$-linear decision tree complexity of 3SUM is $O(n^{3/2})$, and that the randomized $(2k-2)$-linear decision tree complexity of $k$-SUM and $k$-LDT is $O(n^{k/2})$, for any odd $kge3$. These bounds improve (albeit randomized) the corresponding $O(n^{3/2}sqrtlogn)$ and $O(n^{k/2}sqrtlogn)$ decision tree bounds obtained by Gr{o}nlund and Pettie. Our technique includes a specialized randomized variant of fractional cascading data structure. Additionally, we give another deterministic algorithm for 3SUM that runs in $O(n^{2}loglogn/logn)$ time. The latter bound matches a recent independent bound by Freund [Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use of word-RAM model.

Recommendations

• Threesomes, degenerates, and love triangles
• Improved subquadratic 3SUM
• Solving k-SUM using few linear queries
• Deterministic time-space trade-offs for k-SUM
• Subquadratic algorithms for algebraic 3SUM

Cites work

• A nearly quadratic bound for the decision tree complexity of k-SUM
• Consequences of Faster Alignment of Sequences
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Deterministic time-space trade-offs for k-SUM
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• Higher lower bounds from the 3SUM conjecture
• How good is the information theory bound in sorting?
• scientific article; zbMATH DE number 910895 (Why is no real title available?)
• Improved subquadratic 3SUM
• Lower bounds for linear degeneracy testing
• Matching triangles and basing hardness on an extremely popular conjecture
• Mind the gap: essentially optimal algorithms for online dictionary matching with one gap
• Near-optimal linear decision trees for k-SUM and related problems
• Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
• On k-convex polygons
• On a class of \(O(n^ 2)\) problems in computational geometry
• On hardness of jumbled indexing
• On the complexity of k-SAT
• Partition of Space
• Pattern matching under polynomial transformation
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Preprocessing chains for fast dihedral rotations is hard or even impossible.
• Solving k-SUM using few linear queries
• Threesomes, degenerates, and love triangles
• Towards polynomial lower bounds for dynamic problems
• Which problems have strongly exponential complexity?

Cited in

(24)

• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Geometric pattern matching reduces to \(k\)-SUM
• Subquadratic algorithms for algebraic 3SUM
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Time and space efficient collinearity indexing
• Space-efficient randomized algorithms for k-sum
• Connectivity oracles for graphs subject to vertex failures
• Threesomes, degenerates, and love triangles
• A nearly quadratic bound for the decision tree complexity of k-SUM
• Deterministic time-space trade-offs for k-SUM
• Solving k-SUM using few linear queries
• A subquadratic algorithm for 3XOR
• On Multidimensional and Monotone k-SUM
• Improved subquadratic 3SUM
• Near-optimal linear decision trees for k-SUM and related problems
• Near-optimal linear decision trees for \(k\)-SUM and related problems
• Geometric Pattern Matching Reduces to k-SUM.
• Improved algebraic degeneracy testing
• \(k\)-SUM in the sparse regime: complexity and applications
• On Wagner's k-tree algorithm over integers
• Deterministic 3SUM-hardness
• Improved algebraic degeneracy testing
• Exploring the approximability landscape of 3SUM

This page was built for publication: Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy

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