License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.37
URN: urn:nbn:de:0030-drops-95000
URL: http://drops.dagstuhl.de/opus/volltexte/2018/9500/
Go to the corresponding LIPIcs Volume Portal


Goldstein, Isaac ; Lewenstein, Moshe ; Porat, Ely

Improved Space-Time Tradeoffs for kSUM

pdf-format:
LIPIcs-ESA-2018-37.pdf (0.4 MB)


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 well-studied SUBSET-SUM 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 SUBSET-SUM. Recently, improved time-space 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 time-space tradeoff for kSUM. A major ingredient in achieving these results is a general self-reduction 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^{k-delta 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^{k-delta sqrt{k}}) time and using O(n^{delta}) space, for 0 <= delta <= 1. (iii) A space-time 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 read-only access to random bits.

BibTeX - Entry

@InProceedings{goldstein_et_al:LIPIcs:2018:9500,
  author =	{Isaac Goldstein and Moshe Lewenstein and Ely Porat},
  title =	{{Improved Space-Time Tradeoffs for kSUM}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9500},
  URN =		{urn:nbn:de:0030-drops-95000},
  doi =		{10.4230/LIPIcs.ESA.2018.37},
  annote =	{Keywords: kSUM, space-time tradeoff, self-reduction}
}

Keywords: kSUM, space-time tradeoff, self-reduction
Seminar: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 08.08.2018


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI