Cardinal, Jean ;
Iacono, John ;
Ooms, Aurélien
Solving kSUM Using Few Linear Queries
Abstract
The kSUM problem is given n input real numbers to determine whether any k of them sum to zero. The problem is of tremendous importance in the emerging field of complexity theory within P, and it is in particular open whether it admits an algorithm of complexity O(n^c) with c<d where d is the ceiling of k/2. Inspired by an algorithm due to Meiser (1993), we show that there exist linear decision trees and algebraic computation trees of depth O(n^3 log^2 n) solving kSUM. Furthermore, we show that there exists a randomized algorithm that runs in ~O(n^{d+8}) time, and performs O(n^3 log^2 n) linear queries on the input. Thus, we show that it is possible to have an algorithm with a runtime almost identical (up to the +8) to the best known algorithm but for the first time also with the number of queries on the input a polynomial that is independent of k. The O(n^3 log^2 n) bound on the number of linear queries is also a tighter bound than any known algorithm solving kSUM, even allowing unlimited total time outside of the queries. By simultaneously achieving few queries to the input without significantly sacrificing runtime visavis known algorithms, we deepen the understanding of this canonical problem which is a cornerstone of complexitywithinP.
We also consider a range of tradeoffs between the number of terms involved in the queries and the depth of the decision tree. In particular, we prove that there exist o(n)linear decision trees of depth ~O(n^3) for the
kSUM problem.
BibTeX  Entry
@InProceedings{cardinal_et_al:LIPIcs:2016:6376,
author = {Jean Cardinal and John Iacono and Aur{\'e}lien Ooms},
title = {{Solving kSUM Using Few Linear Queries}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {25:125:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6376},
URN = {urn:nbn:de:0030drops63763},
doi = {10.4230/LIPIcs.ESA.2016.25},
annote = {Keywords: kSUM problem, linear decision trees, point location, $varepsilon$nets}
}
2016
Keywords: 

kSUM problem, linear decision trees, point location, $varepsilon$nets 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

2016 