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

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: |
| ||||||

ORCID: |
| ||||||

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: |
| ||||||

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