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

2025/03/27 by Mina Dalirrooyfard, Dalirrooyfard, Mina, Andrea Lincoln +5 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2503.21951

openalex publication_date 2025/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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-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 parity-k-XOR is n^Ω(√(k)) average-case hard, under the k-XOR hypothesis. 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.

Cited by

• k-SUM Hardness Implies Treewidth-SETH
• The Planted Orthogonal Vectors Problem

Related

• On the Hardness of Average-case k-SUM
• On the Fine-Grained Complexity of Parity Problems
• k-SUM in the Sparse Regime
• On learning k-parities with and without noise
• Direct Sums for Parity Decision Trees