Metraipolis › archive › dc_01223c8891ee
On the Hardness of $4$-to-$1$ Games with Perfect Completeness — arXiv:2610.12378
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.12378
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T06:36:30.682Z
- SHA-256 of the archived text
e0489533d2c281191e9c9a70f125d4c6c8abcbc4ecfb81ebd422c240bb7e5dae- Stable URL of this page
https://metraipolis.com/documento/dc_01223c8891ee
How to cite
On the Hardness of $4$-to-$1$ Games with Perfect Completeness — arXiv:2610.12378 — arXiv (en), https://arxiv.org/abs/2610.12378 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_01223c8891ee (Metraipolis archive dc_01223c8891ee, sha256 e0489533d2c281191e9c9a70f125d4c6c8abcbc4ecfb81ebd422c240bb7e5dae)
BibTeX
@misc{dc01223c8891ee,
title = {On the Hardness of $4$-to-$1$ Games with Perfect Completeness — arXiv:2610.12378},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.12378},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_01223c8891ee; sha256 e0489533d2c281191e9c9a70f125d4c6c8abcbc4ecfb81ebd422c240bb7e5dae},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.12378. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We prove that for all $\varepsilon>0$, there exists a positive integer $k$ such that given a $4$-to-$1$ game $\Psi$ with alphabet size at most $k$, it is $\mathbf{NP}$-hard to distinguish between the case that $\mathrm{val}(\Psi)=1$ and the case that $\mathrm{val}(\Psi)\leq \varepsilon$. This confirms the $4$-to-$1$ Games Conjecture from [Khot, \textit{CCC 2002}]. Previously, the best known result, due to [Dinur, Khot, Kindler, Minzer, Safra], established the almost-perfect completeness version (but applied to the stricter problem of $2$-to-$1$ games). Using results from the literature, we get the following implications: (1) for all $k\in \mathbb{N}$, given a $3$-colorable graph $G$, it is $\mathbf{NP}$-hard to find a proper $k$-coloring; (2) for all $\delta>0$, given a $2$-colorable $3$-uniform hypergraph $G$, it is $\mathbf{NP}$-hard to find in it an independent set containing at least $\delta$ fraction of the vertices. Our proof is a three-step construction that builds on the two-step framework of [Dinur, Khot, Kindler, Minzer, Safra]. In the outer-PCP step, we use quadratic equations to gain perfect completeness. We then construct a new middle PCP that performs low-rank tests while preserving a key covering property. Finally, we construct a new inner PCP based on a tensor of the standard Grassmann encoding with its low-rank variant due to [Golowich, FOCS 2023].
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.12378 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:57:31.396Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).