Personal tools
You are here: Home CG seminar Spring 2017 Near optimal algorithms in the linear decision tree model for k-SUM and related problems: The Kane-Lovett-Moran paper
« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930
Log in


Forgot your password?
 

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

underline

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

Micha Sharir, TAU

 

[For the slides click here]

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