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

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)

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

• scientific article; zbMATH DE number 910895 (Why is no real title available?)
• 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?
• 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
• POLYGON CONTAINMENT AND TRANSLATIONAL IN-HAUSDORFF-DISTANCE BETWEEN SEGMENT SETS ARE 3SUM-HARD
• Partition of Space
• Pattern matching under polynomial transformation
• 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

(20)

• Deterministic time-space trade-offs for \(k\)-SUM
• Solving \(k\)-SUM using few linear queries
• 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
• Geometric Pattern Matching Reduces to k-SUM.
• Threesomes, degenerates, and love triangles
• On Multidimensional and Monotone k-SUM
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• Improved algebraic degeneracy testing
• \(k\)-SUM in the sparse regime: complexity and applications
• A nearly quadratic bound for the decision tree complexity of \(k\)-SUM
• Time and space efficient collinearity indexing
• Near-optimal linear decision trees for k-SUM and related problems
• A subquadratic algorithm for 3XOR
• Improved subquadratic 3SUM
• Connectivity oracles for graphs subject to vertex failures
• Near-optimal linear decision trees for \(k\)-SUM and related problems
• Subquadratic algorithms for some \textsc{3sum}-hard geometric problems in the algebraic decision-tree model
• Space-efficient randomized algorithms for \(k\)-sum

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)