Near Optimal Hardness of Approximating $k$-CSP
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908617010053120 |
|---|---|
| author | Minzer, Dor Zheng, Kai Zhe |
| author_facet | Minzer, Dor Zheng, Kai Zhe |
| contents | We show that for every $k\in\mathbb{N}$ and $\varepsilon>0$, for large enough alphabet $R$, given a $k$-CSP with alphabet size $R$, it is NP-hard to distinguish between the case that there is an assignment satisfying at least $1-\varepsilon$ fraction of the constraints, and the case no assignment satisfies more than $1/R^{k-1-\varepsilon}$ of the constraints. This result improves upon prior work of [Chan, Journal of the ACM 2016], who showed the same result with weaker soundness of $O(k/R^{k-2})$, and nearly matches the trivial approximation algorithm that finds an assignment satisfying at least $1/R^{k-1}$ fraction of the constraints.
Our proof follows the approach of a recent work by the authors, wherein the above result is proved for $k=2$. Our main new ingredient is a counting lemma for hyperedges between pseudo-random sets in the Grassmann graphs, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_23991 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near Optimal Hardness of Approximating $k$-CSP Minzer, Dor Zheng, Kai Zhe Computational Complexity We show that for every $k\in\mathbb{N}$ and $\varepsilon>0$, for large enough alphabet $R$, given a $k$-CSP with alphabet size $R$, it is NP-hard to distinguish between the case that there is an assignment satisfying at least $1-\varepsilon$ fraction of the constraints, and the case no assignment satisfies more than $1/R^{k-1-\varepsilon}$ of the constraints. This result improves upon prior work of [Chan, Journal of the ACM 2016], who showed the same result with weaker soundness of $O(k/R^{k-2})$, and nearly matches the trivial approximation algorithm that finds an assignment satisfying at least $1/R^{k-1}$ fraction of the constraints. Our proof follows the approach of a recent work by the authors, wherein the above result is proved for $k=2$. Our main new ingredient is a counting lemma for hyperedges between pseudo-random sets in the Grassmann graphs, which may be of independent interest. |
| title | Near Optimal Hardness of Approximating $k$-CSP |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2510.23991 |