- Info

#
A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM

### Wednesday, December 28th, 2016, 16:10

### Schreiber 309

### A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM

### Esther Ezra, Georgia Tech

### Abstract:

We show that the k-SUM problem can be solved by a linear decision
tree of depth O(n^2 \log^2{n}), improving the recent bound O(n^{3}
\log^3{n}) of Cardinal etal. Our bound depends linearly on k, and allows
us to conclude that the number of linear queries
required to decide the n-dimensional Knapsack or SubsetSum problems is
only O(n^3 \log{n}), improving the currently best known bounds by a
factor of n. Our algorithm extends to the RAM model, showing that the
k-SUM problem can be solved in expected polynomial
time, for any fixed k, with the above bound on the number of linear
queries. Our approach relies on a new point-location mechanism,
exploiting ``Epsilon-cuttings'' that are based on vertical
decompositions in hyperplane arrangements in high dimensions. A major
side result of our analysis is a sharper bound on the complexity of the
vertical decomposition of such an arrangement (in terms of its
dependence on the dimension).

Joint work with Micha Sharir.