A nearly quadratic bound for the decision tree complexity of k-SUM

DOI10.4230/LIPICS.SOCG.2017.41MaRDI QIDQ4580116zbMATH OpenOpenAlexFDO

Authors Esther Ezra, Micha Sharir

Publication date 13 August 2018

Full work available at URL https://doi.org/10.4230/LIPIcs.SoCG.2017.41

zbMATH Keywords

hyperplane arrangementspoint-locationlinear decision tree\(k\)-SUM\(\varepsilon\)-cuttings\(k\)-LDTvertical decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

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

Cited in

(7)

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

This page was built for publication: A nearly quadratic bound for the decision tree complexity of \(k\)-SUM

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