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 \log^2 n)$ linear queries.
Moreover, the queries we use are comparison ... more >>>