Near optimal algorithms in the linear decision tree model for k-SUM and related problems: The Kane-Lovett-Moran paper
Wednesday, August 16th, 2017 16:10
Schreiber 309
Near optimal algorithms in the linear decision tree model for k-SUM and related problems: The Kane-Lovett-Moran paper
Micha Sharir, TAU
Abstract:
We present the recent breakthrough paper of Kane, Lovett and Moran (arXiv, 2017),
which gives nearly optimal algorithms for k-SUM and related problems in the linear decision tree model.
In this problem we are given n real numbers and want to determine whether there exist k among them that sum up to 0.
In the model we only count linear sign tests involving the input numbers. All other operations are for free, but they are not
allowed to access the input explicitly.
[KLM'17] solves k-SUM with O(kn\log^2 n) linear tests, each of which is 2k-sparse (has at most 2k nonzero terms),
with only +1,-1 coefficients.
The same technique can sort A+B, for sets A,B or n real numbers each, with O(n\log^2 n) linear tests, all 8-sparse
with +1,-1 coefficients, and several other problems of this sort, including SubsetSum (with O(n^2\log n) linear tests).
These results improve earlier results by roughly a factor of n.
The paradigm in [KLM'17], as in all earlier works, is to regard the input set (x1,x2,...,xn) as a point in R^n, regard each
test that we want to perform (e.g., that k concrete input elements add up to 0) as an equation of a hyperplane in R^n,
and solve the resulting problem of point location in the arrangement of these hyperplanes.
The novelty in [KLM'17] is the use of a new tool, inferences and inference dimension, introduced by the authors in their study of active learning.