Abstract
In this work, we show the first worstcase to averagecase reduction for the classical kSUM problem. A kSUM instance is a collection of m integers, and the goal of the kSUM problem is to find a subset of k integers that sums to 0. In the averagecase version, the m elements are chosen uniformly at random from some interval [u,u].
We consider the total setting where m is sufficiently large (with respect to u and k), so that we are guaranteed (with high probability) that solutions must exist. In particular, m = u^{Ω(1/k)} suffices for totality. Much of the appeal of kSUM, in particular connections to problems in computational geometry, extends to the total setting.
The best known algorithm in the averagecase total setting is due to Wagner (following the approach of BlumKalaiWasserman), and achieves a running time of u^{Θ(1/log k)} when m = u^{Θ(1/log k)}. This beats the known (conditional) lower bounds for worstcase kSUM, raising the natural question of whether it can be improved even further. However, in this work, we show a matching averagecase lower bound, by showing a reduction from worstcase lattice problems, thus introducing a new family of techniques into the field of finegrained complexity. In particular, we show that any algorithm solving averagecase kSUM on m elements in time u^{o(1/log k)} will give a superpolynomial improvement in the complexity of algorithms for lattice problems.
BibTeX  Entry
@InProceedings{brakerski_et_al:LIPIcs.APPROX/RANDOM.2021.29,
author = {Brakerski, Zvika and StephensDavidowitz, Noah and Vaikuntanathan, Vinod},
title = {{On the Hardness of AverageCase kSUM}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {29:129:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14722},
URN = {urn:nbn:de:0030drops147223},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.29},
annote = {Keywords: kSUM, finegrained complexity, averagecase hardness}
}
Keywords: 

kSUM, finegrained complexity, averagecase hardness 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) 
Issue Date: 

2021 
Date of publication: 

15.09.2021 