Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
From MaRDI portal
Publication:5111730
DOI10.4230/LIPIcs.ESA.2017.42zbMath1442.68070arXiv1512.05279OpenAlexW2963956072MaRDI QIDQ5111730
Publication date: 27 May 2020
Full work available at URL: https://arxiv.org/abs/1512.05279
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