License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.58
URN: urn:nbn:de:0030-drops-62250
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6225/
Lincoln, Andrea ;
Vassilevska Williams, Virginia ;
Wang, Joshua R. ;
Williams, R. Ryan
Deterministic Time-Space Trade-Offs for k-SUM
Abstract
Given a set of numbers, the k-SUM problem asks for a subset of k numbers that sums to zero. When the numbers are integers, the time and space complexity of k-SUM is generally studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point. We present a time and space efficient deterministic self-reduction for the k-SUM problem which holds for both models, and has many interesting consequences. To illustrate:
- 3-SUM 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 polylogarithmic-time improvement over quadratic time for 3-SUM can be converted into an algorithm with an identical time improvement but low space complexity as well.
- 3-SUM is in deterministic time O(n^2) and space O(sqrt(n)), derandomizing an algorithm of Wang.
- A popular conjecture states that 3-SUM requires n^{2-o(1)} time on the word-RAM. We show that the 3-SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every O(n^{.51})-space algorithm for 3-SUM requires at least n^{2-o(1)} time on the word-RAM.
- For k >= 4, k-SUM is in deterministic O(n^{k-2+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 Time-Space Trade-Offs for k-SUM}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {58:1--58:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-013-2},
ISSN = {1868-8969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6225},
URN = {urn:nbn:de:0030-drops-62250},
doi = {10.4230/LIPIcs.ICALP.2016.58},
annote = {Keywords: 3SUM, kSUM, time-space tradeoff, algorithm}
}
|
Keywords: |
|
3SUM, kSUM, time-space tradeoff, algorithm |
|
Collection: |
|
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
23.08.2016 |
