Near optimal algorithms in the linear decision tree model for k-SUM and related problems: The Kane-Lovett-Moran paper

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.