Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More

This work establishes conditional lower bounds for average-case parity-counting versions of the problems k-XOR, k-SUM, and k-OV. The main contribution is a set of self-reductions for the problems, providing the first specific distributions, for which:

• parity-k-OV is n Ω( √ k) average-case hard, under the k-OV hypothesis (and hence under SETH),

• parity-k-SUM is n Ω( √ k) average-case hard, under the k-SUM hypothesis, and

Under the very believable hypothesis that at least one of the k-OV, k-SUM, k-XOR or k-Clique hypotheses is true, we show that parity-k-XOR, parity-k-SUM, and parity-k-OV all require at least n Ω(k 1/3 ) (and sometimes even more) time on average (for specific distributions).

To achieve these results, we present a novel and improved framework for worst-case to average-case fine-grained reductions, building on the work of Dalirooyfard, Lincoln, and Vassilevska Williams, FOCS 2020.