On the k-SUM problem

Combinatorics Seminar
Friday, October 21, 2016 - 15:05
1 hour (actually 50 minutes)
Skiles 005
Georgia Tech

Joint work with Micha Sharir (Tel-Aviv University).

Following a recent improvement of Cardinal etal. on the complexity of a linear decision tree for k-SUM, resulting in O(n^3 \log^3{n}) linear queries, we present a further improvement to O(n^2 \log^2{n}) such queries. Our approach exploits a point-location mechanism in arrangements of hyperplanes in high dimensions, and, in fact, brings a new view to such mechanisms. In this talk I will first present a background on the k-SUM problem, and then discuss bottom-vertex triangulation and vertical decomposition of arrangements of hyperplanes and how they serve our analysis.