Goldstein, Isaac ;
Lewenstein, Moshe ;
Porat, Ely
Improved SpaceTime Tradeoffs for kSUM
Abstract
In the kSUM problem we are given an array of numbers a_1,a_2,...,a_n and we are required to determine if there are k different elements in this array such that their sum is 0. This problem is a parameterized version of the wellstudied SUBSETSUM problem, and a special case is the 3SUM problem that is extensively used for proving conditional hardness. Several works investigated the interplay between time and space in the context of SUBSETSUM. Recently, improved timespace tradeoffs were proven for kSUM using both randomized and deterministic algorithms.
In this paper we obtain an improvement over the best known results for the timespace tradeoff for kSUM. A major ingredient in achieving these results is a general selfreduction from kSUM to mSUM where m<k, and several useful observations that enable this reduction and its implications. The main results we prove in this paper include the following: (i) The best known Las Vegas solution to kSUM running in approximately O(n^{kdelta sqrt{2k}}) time and using O(n^{delta}) space, for 0 <= delta <= 1. (ii) The best known deterministic solution to kSUM running in approximately O(n^{kdelta sqrt{k}}) time and using O(n^{delta}) space, for 0 <= delta <= 1. (iii) A spacetime tradeoff for solving kSUM using O(n^{delta}) space, for delta>1. (iv) An algorithm for 6SUM running in O(n^4) time using just O(n^{2/3}) space. (v) A solution to 3SUM on random input using O(n^2) time and O(n^{1/3}) space, under the assumption of a random readonly access to random bits.
BibTeX  Entry
@InProceedings{goldstein_et_al:LIPIcs:2018:9500,
author = {Isaac Goldstein and Moshe Lewenstein and Ely Porat},
title = {{Improved SpaceTime Tradeoffs for kSUM}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {37:137:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9500},
URN = {urn:nbn:de:0030drops95000},
doi = {10.4230/LIPIcs.ESA.2018.37},
annote = {Keywords: kSUM, spacetime tradeoff, selfreduction}
}
2018
Keywords: 

kSUM, spacetime tradeoff, selfreduction 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

2018 