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.ESA.2017.42
URN: urn:nbn:de:0030-drops-78364
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7836/
Gold, Omer ;
Sharir, Micha
Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy
Abstract
Given a set of n real numbers, the 3SUM problem is to decide whether there are three of them that sum to zero. Until a recent breakthrough by Gronlund and Pettie [FOCS'14], a simple Theta(n^2)-time deterministic algorithm for this problem was conjectured to be optimal. Over the years many algorithmic problems have been shown to be reducible from the 3SUM problem or its variants, including the more generalized forms of the problem, such as k-SUM and k-variate linear degeneracy testing (k-LDT). The conjectured hardness of these problems have become extremely popular for basing conditional lower bounds for numerous algorithmic problems in P.
In this paper, we show that the randomized 4-linear decision tree complexity of 3SUM is O(n^{3/2}), and that the randomized (2k-2)-linear decision tree complexity of k-SUM and k-LDT is O(n^{k/2}), for any odd >= 3. These bounds improve (albeit randomized) the corresponding O(n^{3/2} sqrt{log n}) and O(n^{k/2} sqrt{log n}) decision tree bounds obtained by Gr{\o}nlund and Pettie. Our technique includes a specialized randomized variant of fractional cascading data structure. Additionally, we give another deterministic algorithm for 3SUM that runs in O(n^2 log log n / log n ) time. The latter bound matches a recent independent bound by Freund [Algorithmica 2017], but our algorithm is somewhat simpler, due to a better use of the word-RAM model.
BibTeX - Entry
@InProceedings{gold_et_al:LIPIcs:2017:7836,
author = {Omer Gold and Micha Sharir},
title = {{Improved Bounds for 3SUM, k-SUM, and Linear Degeneracy}},
booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)},
pages = {42:1--42:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-049-1},
ISSN = {1868-8969},
year = {2017},
volume = {87},
editor = {Kirk Pruhs and Christian Sohler},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7836},
URN = {urn:nbn:de:0030-drops-78364},
doi = {10.4230/LIPIcs.ESA.2017.42},
annote = {Keywords: 3SUM, k-SUM, Linear Degeneracy, Linear Decision Trees, Fractional Cascading}
}
|
Keywords: |
|
3SUM, k-SUM, Linear Degeneracy, Linear Decision Trees, Fractional Cascading |
|
Collection: |
|
25th Annual European Symposium on Algorithms (ESA 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.09.2017 |
