Near-Optimal UGC-hardness of Approximating Max k-CSP_R

Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan

In this paper, we prove an almost-optimal hardness for Max $k$-CSP${}_R$ based on Khot's Unique Games Conjecture (UGC). In Max $k$-CSP${}_R$, we are given a set of predicates each of w…