Near Optimal Hardness of Approximating k-CSP

We show that for every k∈ℕ and ε>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−ε fraction of the constraints, and the case no assignment satisfies more than 1/Rk−1−ε 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/Rk−2), and nearly matches the trivial approximation algorithm that finds an assignment satisfying at least 1/Rk−1 fraction of the constraints. Our proof follows the approach of a recent work [Minzer and Zheng, STOC 2024] of 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.