Max-CSPs on large alphabets. There is a vast literature which study CSPs on non-boolean alphabets. For arity the setting of arity 2, Kindler, Kolla and Trevisan [1]} gave a \(\Omega ((1/R)\log R)\) -approximation algorithm, this matches the Unique Games based hardness from [2]}. For the setting of larger arities, Makarychev and Makarychev [3]} gave a \(\Omega (k/R^{k-1})\) -approximation algorithm, which is tight for the setting of \(k \ge R\)  from the work of Chan [4]}. For the setting of small \(k \le R\) , the best known lower bound is the Unique Games based \(\Omega (R^{-(k-1)}(\log R)^{k/2})\) -hardness by Manurangsi, Nakkiran and Trevisan [5]}, for which they also give a \(O(R^{-(k-1)}\log R)\) -approximation algorithm. The tightest known lower bound is due to the work of [6]}, whose result along with a known \(R^{-k + 1}\) -integrality gap for linear programs implies a \(\Omega (k^3 R^{-(k-1)} \log R)\) -hardness for 2-CSPs assuming UGC.
