$k$-SUM in the Sparse Regime

Shweta Agrawal, Sagnik Saha, Nikolaj I. Schwartzbach +2

In the average-case $k$-SUM problem, given $r$ integers chosen uniformly at random from $\{0,\dots ,M-1\}$, the objective is to find a ``solution'' set of $k$ numbers that sum to $0…