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

DOI10.4230/LIPICS.ESA.2017.42zbMATH Open1442.68070arXiv1512.05279OpenAlexW2963956072MaRDI QIDQ5111730FDOQ5111730

Omer Gold, Micha Sharir

Publication date: 27 May 2020

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.

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

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

zbMATH Keywords

3SUMlinear degeneracyfractional cascadinglinear decision trees\(k\)-SUM

Mathematics Subject Classification ID

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

Cites Work

• Which problems have strongly exponential complexity?
• On a class of \(O(n^ 2)\) problems in computational geometry
• Towards polynomial lower bounds for dynamic problems
• Threesomes, Degenerates, and Love Triangles
• Lower bounds for linear degeneracy testing
• On the complexity of \(k\)-SAT
• Constructing Arrangements of Lines and Hyperplanes with Applications
• On Hardness of Jumbled Indexing
• On \(k\)-convex polygons
• Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
• Fractional cascading. I: A data structuring technique
• Partition of Space
• Preprocessing chains for fast dihedral rotations is hard or even impossible.
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Fractional cascading. II: Applications
• Pattern matching under polynomial transformation
• Title not available (Why is that?)
• Improved subquadratic 3SUM
• How good is the information theory bound in sorting?
• Consequences of Faster Alignment of Sequences
• Higher Lower Bounds from the 3SUM Conjecture
• Solving k-SUM using few linear queries
• Title not available (Why is that?)
• Mind the Gap: Essentially Optimal Algorithms for Online Dictionary Matching with One Gap
• Near-optimal linear decision trees for k-SUM and related problems
• Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
• A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM

Cited In (11)

• Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
• Subquadratic algorithms for algebraic 3SUM
• Geometric pattern matching reduces to \(k\)-SUM
• Connectivity Oracles for Graphs Subject to Vertex Failures
• Geometric Pattern Matching Reduces to k-SUM.
• On Multidimensional and Monotone k-SUM
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• \(k\)-SUM in the sparse regime: complexity and applications
• Time and space efficient collinearity indexing
• A subquadratic algorithm for 3XOR
• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model

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)