In the average-case k-SUM problem, given r integers chosen uniformly at random from \{0,\ldots,M-1\}, the objective is to find a set of k numbers that sum to 0 modulo M (this set is called a ``solution''). In the related k-XOR problem, given k uniformly random Boolean vectors of length \log{M}, ... more >>>