Personal tools
You are here: Home CG seminar Fall 2017 A Nearly Quadratic Bound for the Decision Tree Complexity of k-SUM
« September 2017 »
September
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
Log in


Forgot your password?
 

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

Wednesday, December 28th, 2016, 16:10

Schreiber 309

underline

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.
Document Actions