Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy

DOI10.4230/LIPIcs.ESA.2017.42zbMath1442.68070arXiv1512.05279OpenAlexW2963956072MaRDI QIDQ5111730

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) Analysis of algorithms (68W40) Data structures (68P05) Randomized algorithms (68W20)

Related Items

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 ⋮ A subquadratic algorithm for 3XOR ⋮ Geometric Pattern Matching Reduces to k-SUM. ⋮ Connectivity Oracles for Graphs Subject to Vertex Failures ⋮ On Multidimensional and Monotone k-SUM ⋮ 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

Cites Work

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