OpenAlex ·
On the Hardness of $4$-to-$1$ Games with Perfect Completeness
- Published
- Source
- OpenAlex
- Published in
- arXiv (Cornell University)
- DOI
- 10.48550/arxiv.2610.12378
- Original
- Read it at the publisher
- Topics
Abstract
We prove that for all $\varepsilon>0$, there exists a positive integer $k$ such that given a $4$-to-$1$ game $Ψ$ with alphabet size at most $k$, it is $\mathbf{NP}$-hard to distinguish between the case that $\mathrm{val}(Ψ)=1$ and the case that $\mathrm{val}(Ψ)\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 $δ>0$, given a $2$-colorable $3$-uniform hypergraph $G$, it is $\mathbf{NP}$-hard to find in it an independent set containing at least $δ$ 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].
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
The chromatic number of the associahedron: simple and logarithmic
Quantum-assisted rendezvous on hypercubes: a quantum Bernoulli noise approach
Mutually unbiased bases: common states, completion, and extension obstructions
Polynomial directed treewidth forces a large bramble with congestion two
Subspace Uncertainty and Sharp Sampling Thresholds on the Boolean Cube
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.