本文通过条件假设证明了 $k$-XOR、$k$-SUM 和 $k$-OV 的奇偶计数版本在平均情况下的下界。主要贡献是一组针对这些问题的自归约方法，提供了第一个特定分布下的结果：在 $k$-OV 假设（以及由此推导出的 SETH）下，$\mathsf{parity}\text{-}k\text{-}OV$ 在平均情况下具有 $n^{\Omega(\sqrt{k})}$ 的下界；在 $k$-SUM 假设下，$\mathsf{parity}\text{-}k\text{-}SUM$ 具有 $n^{\Omega(\sqrt{k})}$ 的平均情况下界；在 $k$-XOR 假设下，$\mathsf{parity}\text{-}k\text{-}XOR$ 具有 $n^{\Omega(\sqrt{k})}$ 的平均情况下界。假设至少有一个 $k$-OV、$k$-SUM、$k$-XOR 或 $k$-Clique 假设为真，则我们证明了 $\mathsf{parity}\text{-}k\text{-}XOR$、$\mathsf{parity}\text{-}k\text{-}SUM$ 和 $\mathsf{parity}\text{-}k\text{-}OV$ 在特定分布下需要至少 $n^{\Omega(k^{1/3})}$（有时甚至更多）的时间。为了实现这些结果，我们提出了一种改进的最坏情况到平均情况的精细归约框架，基于 Dalirooyfard、Lincoln 和 Vassilevska Williams 在 FOCS 2020 中的工作。

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: $\mathsf{parity}\text{-}k\text{-}OV$ is $n^{\Omega(\sqrt{k})}$ average-case hard, under the $k$-OV hypothesis (and hence under SETH), $\mathsf{parity}\text{-}k\text{-}SUM$ is $n^{\Omega(\sqrt{k})}$ average-case hard, under the $k$-SUM hypothesis, and $\mathsf{parity}\text{-}k\text{-}XOR$ is $n^{\Omega(\sqrt{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^{\Omega(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.