Near Optimal Hardness of Approximating k k -CSP

Dor Minzer, Kai Zhe Zheng · 2025

Read Near Optimal Hardness of Approximating k k -CSP by Dor Minzer, Kai Zhe Zheng (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-23991.txt.

Introduction

Dor Minzer and a co-author prove near-optimal hardness for approximating constraint satisfaction problems with many variables per constraint. A k-CSP asks for an assignment satisfying as many constraints as possible. A trivial algorithm satisfies a one-over-R-to-the-k-minus-one fraction by guessing, where R is the alphabet size. The question is whether anything smarter is possible.

The answer, for large alphabets, is no. It is NP-hard to distinguish instances where every constraint can be satisfied from instances where nothing beats the trivial fraction by more than a hair. This sharpens the result of Chan, whose soundness bound was weaker by a factor of k over R. The proof extends the authors' two-variable argument, and its new tool is a counting lemma for hyperedges between pseudo-random sets in Grassmann graphs. They note the lemma may serve other problems too.

Catalog record

CREATORDor Minzer, Kai Zhe Zheng
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-23991

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Near Optimal Hardness of Approximating k k -CSP Dor Minzer, Kai Zhe Zheng Abstract We show that for every k ∈ ℕ k\in\mathbb{N} and ε > 0 \varepsilon>0 , for large enough alphabet R R , given a k k -CSP with alphabet size R R , it is NP-hard to distinguish between the case that there is an assignment satisfying at least 1 − ε 1-\varepsilon fraction of the constraints, and the case no assignment satisfies more than 1 / R k − 1 − ε 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 ) O(k/R^{k-2}) , and nearly matches the trivial approximation algorithm that finds an assignment satisfying at least 1 / R k − 1 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 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. 1 Introduction The PCP theorem [ FGL+96 , AS98 , ALM+98 ] is a cornerstone result in the theory of computation with applications and connections to hardness of approximation, cryptography, pseudorandomness, analysis and more. It has many equivalent formulations, and for this paper it will be convenient to state it in the language of constraints satisfaction problems (CSPs in short). Definition 1.1 . For an integer k , an instance \Psi of k -CSP consists of a k -uniform hypergraph G=(V,E) , an alphabet \Sigma , and a set of constraints \{\Phi_{e}\}_{e\in E} . Each constraint is a map \Phi_{e}:\Sigma^{k}\to\{0,1\} , where the set of tuples \Phi_{e}^{-1}(1) is thought of as assignments to the vertices of e that satisfy the constraints on e . The arity parameter k and the alphabet size parameter |\Sigma| will be important for the purposes of this paper. Given a k -CSP instance \Psi we define its value as \val(\Psi)=\max_{A:V\to\Sigma}\frac{|\{e=(v_{1},\ldots,v_{k})\;|\;\Phi_{e}(A(v_{1}),\ldots,A(v_{k}))=1\}|}{|E|}. Using the language of CSPs, the basic PCP theorem [ FGL+96 , AS98 , ALM+98 ] combined with Raz’s parallel repetition theorem [ Raz98 ] gives the following result: Theorem 1.2 . There exists \gamma>0 such that for sufficiently large R , given an instance \Psi of 2 -CSP with alphabet size R , it is NP-hard to distinguish the following two cases: • YES case: {\sf val}(\Psi)=1 . • NO case: {\sf val}(\Psi)\leqslant\frac{1}{R^{\gamma}} . Let k>2 . Since any 2 -CSP can be phrased as a k -CSP, it is clear that the above hardness result applies to k -CSPs as well. However, one expects a stronger hardness result to hold. Indeed, if \Psi is a 2 -CSP, then taking all subsets of k/2 constraints from \Psi and for each one putting the k -ary constraint corresponding to their “and” yields a k -CSP whose value is \val(\Psi)^{k/2} . Thus, 1.2 implies: Theorem 1.3 . There exists \gamma>0 such that for sufficiently large R , for any even integer k , given an instance \Psi of k -CSP with alphabet size R , it is NP-hard to distinguish the following two cases: • YES case: {\sf val}(\Psi)=1 . • NO case: {\sf val}(\Psi)\leqslant\frac{1}{R^{\gamma(k-1)}} . For many hardness of approximation applications, one only needs the soundness to be a vanishing function of the alphabet size, in which case results such as 1.2 and 1.3 are sufficient. For certain cases, however, one additionally requires the soundness to be small relative to the alphabet size [ Lae14 , KS13 , LM24 ] . Optimizing the alphabet-soundness tradeoff for k -query PCPs is the focus of this paper and quantitatively, one can think of improving this tradeoff as increasing the value of \gamma in 1.3 . For this task, one should think of k as a fixed constant, and the goal is to obtain larger, concrete values of \gamma for 1.3 with this arity k . It is clear that the best we can hope in 1.3 is \gamma=1-o(1) . Indeed, any k -CSP of alphabet size R has value at least \frac{1}{R^{k-1}} , as obtained by a randomly chosen assignment. On the other hand, 1.3 only achieves a small but absolute value \gamma>0 , leaving a large gap between its assertion and what is potentially possible. Strictly speaking, this implicit value of \gamma is still the best known result to date. If one is willing to relax the completeness parameter slightly, namely require the value in the YES case to only be close to 1 (as opposed to exactly 1 ), then significantly better values for \gamma in 1.2 are known. Khot and Safra [ KS13 ] showed that one may take \gamma=1/6-o(1) , and this was subsequently improved by Chan [ Cha16 ] , who showed that one may take \gamma=1/2-o(1) . This result was further improved recently in [ MZ24 ] , who achieved the near optimal \gamma=1-o(1) . In the same fashion, for k>2 stronger forms of 1.3 are known to hold, again with imperfect completeness. In this regime, Chan [ Cha16 ] obtains soundness on the orders of \frac{k}{R^{k-2}} if 3\leqslant k<R (which is the most relevant regime for us, as we think of k as a small constant and R as being a large constant) and \frac{k}{R^{k-1}} for R\leqslant k . In terms of \gamma , this roughly translates to \gamma=\frac{k-2}{k-1} , which approaches 1 for sufficiently large k , but is still bounded away from the potentially best possible when k is thought of as constant. This gap is even more pronounced for small constant values of k such as 3 or 4 . In terms of the best approximation ratio possible for k -CSP, it is known that approximating the value of k -CSP within factor O_{k}(\log R/R^{k-1}) is NP-hard [ MNT22 , KS15 ] . The downside of this result is that, when stated as a gap problem, the completeness parameter (the value in the YES case) is small and is a vanishing function of the alphabet size R . Our main result is a hardness result that achieves a slightly weaker approximation ratio than the result of [ MNT22 , KS15 ] , but has completeness close to 1 . Theorem 1.4 . For all \varepsilon,\delta>0 and arity k , and sufficiently large alphabet size R , it is NP-hard to distinguish between the following two cases given a k -CSP \Psi with alphabet size R : • YES case: \val(\Psi)\geqslant 1-\delta , • NO case: \val(\Psi)\leqslant\frac{1}{R^{(1-\varepsilon)(k-1)}} . The fact that the value in the YES case is close to 1 and that the alphabet-soundness tradeoff is nearly optimal leads to improved hardness results for k -Dimensional Matching and related problems. Application to k -Dimensional Matching By plugging our improved k -CSP hardness result into the reduction from [ LST25 ] , we obtain improved hardness of approximation for k -Dimensional matching . Definition 1.5 . A k -Dimensional Matching instance \Pi=(V,E) consists of a k -partite hypergraph G=(V,E) with hyperedges of size at most k . Its value, \val(\Pi) ,

Read the complete text