Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.21951 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909555844186112 |
|---|---|
| author | Dalirrooyfard, Mina Lincoln, Andrea Saha, Barna Williams, Virginia Vassilevska |
| author_facet | Dalirrooyfard, Mina Lincoln, Andrea Saha, Barna Williams, Virginia Vassilevska |
| contents | 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^{Ω(\sqrt{k})}$ average-case hard, under the $k$-OV hypothesis (and hence under SETH),
$\mathsf{parity}\text{-}k\text{-}SUM$ is $n^{Ω(\sqrt{k})}$ average-case hard, under the $k$-SUM hypothesis, and
$\mathsf{parity}\text{-}k\text{-}XOR$ is $n^{Ω(\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^{Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_21951 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More Dalirrooyfard, Mina Lincoln, Andrea Saha, Barna Williams, Virginia Vassilevska Computational Complexity 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^{Ω(\sqrt{k})}$ average-case hard, under the $k$-OV hypothesis (and hence under SETH), $\mathsf{parity}\text{-}k\text{-}SUM$ is $n^{Ω(\sqrt{k})}$ average-case hard, under the $k$-SUM hypothesis, and $\mathsf{parity}\text{-}k\text{-}XOR$ is $n^{Ω(\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^{Ω(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. |
| title | Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2503.21951 |