Near-optimal linear decision trees for k-SUM and related problems

DOI10.1145/3285953MaRDI QIDQ5244388zbMATH OpenOpenAlexFDO

Authors Daniel M. Kane, Shachar Lovett, Shay Moran

Publication date 21 November 2019

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3285953

zbMATH Keywords

comparison querieshyperplane arrangementinference dimensionlinear decision tree

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Data structures (68P05) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Near-optimal linear decision trees for k-SUM and related problems
• A nearly quadratic bound for the decision tree complexity of k-SUM
• Solving k-SUM using few linear queries
• Improved bounds for 3SUM, \(k\)-SUM, and linear degeneracy
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model

Cited in

(15)

• 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
• Time and space efficient collinearity indexing
• scientific article; zbMATH DE number 1700041 (Why is no real title available?)
• A nearly quadratic bound for the decision tree complexity of k-SUM
• Solving k-SUM using few linear queries
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Near-optimal linear decision trees for k-SUM and related problems
• Geometric Pattern Matching Reduces to k-SUM.
• Convex polygon containment: improving quadratic to near linear time
• Deterministic 3SUM-hardness
• Improved algebraic degeneracy testing
• Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees
• A general technique for searching in implicit sets via function inversion

This page was built for publication: Near-optimal linear decision trees for \(k\)-SUM and related problems

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