CaltechAUTHORS
  A Caltech Library Service

On Multidimensional and Monotone k-SUM

Hsu, Chloe Ching-Yun and Umans, Chris (2017) On Multidimensional and Monotone k-SUM. In: 42nd International Symposium on Mathematical Foundations of Computer Science. Leibniz International Proceedings in Informatics. Dagstuhl Publishing , Wadern, Germany, Art. No. 50. ISBN 9783959770460. https://resolver.caltech.edu/CaltechAUTHORS:20191115-144427087

[img] PDF - Published Version
Creative Commons Attribution.

503Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20191115-144427087

Abstract

The well-known k-SUM conjecture is that integer k-SUM requires time Ω(n^([k/2]-o(1)). Recent work has studied multidimensional k-SUM in F^d_p, where the best known algorithm takes time O(n^([k/2]). Bhattacharyya et al. [ICS 2011] proved a min(2^(Ω(d)), n^(Ω(k)) lower bound for k-SUM in F^d_p under the Exponential Time Hypothesis. We give a more refined lower bound under the standard k-SUM conjecture: for sufficiently large p, k-SUM in F^d_p requires time Ω(n^(k/2-o(1)) if k is even, and Ω(n^([k/2]-2k log k/log p –o(1) if k is odd. For a special case of the multidimensional problem, bounded monotone d-dimensional 3SUM, Chan and Lewenstein [STOC 2015] gave a surprising O(n^(2−2/(d+13))) algorithm using additive combinatorics. We show this algorithm is essentially optimal. To be more precise, bounded monotone d-dimensional 3SUM requires time Ω(n^(2−4/d−o(1))) under the standard 3SUM conjecture, and time Ω(n^(2−2/d−o(1))) under the so-called strong 3SUM conjecture. Thus, even though one might hope to further exploit the structural advantage of monotonicity, no substantial improvements beyond those obtained by Chan and Lewenstein are possible for bounded monotone d-dimensional 3SUM.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.4230/LIPIcs.MFCS.2017.50DOIArticle
ORCID:
AuthorORCID
Hsu, Chloe Ching-Yun0000-0002-7743-3168
Additional Information:© 2017 Chloe Ching-Yun Hsu and Christopher Umans; licensed under Creative Commons License CC-BY. Supported by NSF grant CCF-1423544 and a Simons Foundation Investigator grant.
Funders:
Funding AgencyGrant Number
NSFCCF-1423544
Simons FoundationUNSPECIFIED
Subject Keywords:3SUM, kSUM, monotone 3SUM, strong 3SUM conjecture
Series Name:Leibniz International Proceedings in Informatics
Classification Code:1998 ACM Subject Classification: F.2.1 Numerical Algorithms and Problems
Record Number:CaltechAUTHORS:20191115-144427087
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20191115-144427087
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:99871
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:15 Nov 2019 23:02
Last Modified:15 Nov 2019 23:02

Repository Staff Only: item control page