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

Mina Dalirrooyfard, Andrea Lincoln, Barna Saha +1

This work establishes conditional lower bounds for average-case {\em parity}-counting versions of the problems $k$-XOR, $k$-SUM, and $k$-OV. The main contribution is a set of self-…