Lincoln, Andrea ;
Vassilevska Williams, Virginia ;
Wang, Joshua R. ;
Williams, R. Ryan
Deterministic TimeSpace TradeOffs for kSUM
Abstract
Given a set of numbers, the kSUM problem asks for a subset of k numbers that sums to zero. When the numbers are integers, the time and space complexity of kSUM is generally studied in the wordRAM model; when the numbers are reals, the complexity is studied in the realRAM model, and space is measured by the number of reals held in memory at any point. We present a time and space efficient deterministic selfreduction for the kSUM problem which holds for both models, and has many interesting consequences. To illustrate:
 3SUM is in deterministic time O(n^2*lg(lg(n))/lg(n)) and space O(sqrt(n*lg(n)/lg(lg(n)))). In general, any polylogarithmictime improvement over quadratic time for 3SUM can be converted into an algorithm with an identical time improvement but low space complexity as well.
 3SUM is in deterministic time O(n^2) and space O(sqrt(n)), derandomizing an algorithm of Wang.
 A popular conjecture states that 3SUM requires n^{2o(1)} time on the wordRAM. We show that the 3SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every O(n^{.51})space algorithm for 3SUM requires at least n^{2o(1)} time on the wordRAM.
 For k >= 4, kSUM is in deterministic O(n^{k2+2/k}) time and O(sqrt(n)) space.
BibTeX  Entry
@InProceedings{lincoln_et_al:LIPIcs:2016:6225,
author = {Andrea Lincoln and Virginia Vassilevska Williams and Joshua R. Wang and R. Ryan Williams},
title = {{Deterministic TimeSpace TradeOffs for kSUM}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {58:158:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6225},
URN = {urn:nbn:de:0030drops62250},
doi = {10.4230/LIPIcs.ICALP.2016.58},
annote = {Keywords: 3SUM, kSUM, timespace tradeoff, algorithm}
}
23.08.2016
Keywords: 

3SUM, kSUM, timespace tradeoff, algorithm 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

23.08.2016 