Abstract
The wellknown kSUM conjecture is that integer kSUM requires time Omega(n^{\ceil{k/2}o(1)}). Recent work has studied multidimensional kSUM in F_p^d, where the best known algorithm takes time \tilde O(n^{\ceil{k/2}}). Bhattacharyya et al. [ICS 2011] proved a min(2^{\Omega(d)},n^{\Omega(k)}) lower bound for kSUM in F_p^d under the Exponential Time Hypothesis. We give a more refined lower bound under the standard kSUM conjecture: for sufficiently large p, kSUM in F_p^d requires time Omega(n^{k/2o(1)}) if k is even, and Omega(n^{\ceil{k/2}2k(log k)/(log p)o(1)}) if k is odd.
For a special case of the multidimensional problem, bounded monotone ddimensional 3SUM, Chan and Lewenstein [STOC 2015] gave a surprising \tilde O(n^{22/(d+13)}) algorithm using additive combinatorics. We show this algorithm is essentially optimal. To be more precise, bounded monotone ddimensional 3SUM requires time Omega(n^{2\frac{4}{d}o(1)}) under the standard 3SUM conjecture, and time Omega(n^{2\frac{2}{d}o(1)}) under the socalled 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 ddimensional 3SUM.
BibTeX  Entry
@InProceedings{hsu_et_al:LIPIcs:2017:8061,
author = {Chloe ChingYun Hsu and Chris Umans},
title = {{On Multidimensional and Monotone kSUM}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {50:150:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8061},
URN = {urn:nbn:de:0030drops80618},
doi = {10.4230/LIPIcs.MFCS.2017.50},
annote = {Keywords: 3SUM, kSUM, monotone 3SUM, strong 3SUM conjecture}
}
Keywords: 

3SUM, kSUM, monotone 3SUM, strong 3SUM conjecture 
Collection: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) 
Issue Date: 

2017 
Date of publication: 

01.12.2017 