Sparse average-case k-SUM conjecture

In the $(k,N,r)$-SUM problem, the input consists of $r$ elements $z_1,\ldots,z_r$, independently and uniformly chosen from $\{-N,\ldots,N\}$. The goal is to find an ordered $k$-tuple of distinct indices $K=\{i_1,\ldots,i_k\}$ such that

$$\sum_{j\in K}z_j=0,$$

where the sum is over $\mathbb{Z}$. The sparse regime has only a few solutions on average, with $r^k\approx N$. Sparse average-case $k$-SUM conjecture. Any algorithm that solves the $(k,N,r)$-SUM problem with $r=N^{1/k}$ and probability $\Omega_k(1)$ has expected running time at least

$$T=\Omega_k\left(r^{\lceil k/2\rceil-o(1)}\right).$$

The conjecture is presented as folklore hardness of the uniform distribution under a standard computational model and underlies the paper's conditional optimality results for dense $k$-SUM.