On the Decision Tree Complexity of $k$-SUM

In the $k$-SUM problem, we are given $n$ real numbers as input, and we are asked whether there exists a zero-sum $k$-subset. The problem is of tremendous importance in complexity theory, and it is in particular open whether it admits an algorithm of complexity $O(n^c)$ with $c<\lceil k / 2\rceil$. Revisiting a known algorithm due to Meiser (1993), we show that there exist linear decision trees of depth $O(n^3\log^3 n)$ solving this problem. Furthermore, we show that there exists a Las Vegas algorithm that runs in $O(n^{k+1})$ time performing exactly this number of linear queries on the input. We also consider a range of tradeoffs between the number of terms involved in the queries and the depth of the decision tree. In particular, we prove that there exists $o(n)$-linear decision trees of depth $O(n^c)$ for some constant $c$. The query complexities also hold for nonuniform real-RAM algorithms.