2018/06/20 by Daniel M. Kane, Shachar Lovett, Shay Moran · 17 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Computational Geometry and Mesh Generation #Logarithm #Sorting #Construct (python library) #Combinatorics #Mathematics #Decision tree #Variety (cybernetics) #Decision problem #Subset sum problem #Discrete mathematics #Mathematical optimization #Computer science #Algorithm #Statistics #Data mining
paper · pdf · doi:10.1145/3188745.3188770
openalex publication_date 2018/06/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry. For example, for any constant k, we construct linear decision trees that solve the k-SUM problem on n elements using O(n log2 n) linear queries. Moreover, the queries we use are comparison queries, which compare the sums of two k-subsets; when viewed as linear queries, comparison queries are 2k-sparse and have only −1,0,1 coefficients. We give similar constructions for sorting sumsets A+B and for solving the SUBSET-SUM problem, both with optimal number of queries, up to poly-logarithmic terms.