This paper studies how well the standard LP relaxation approximates a k -ary constraint satisfaction problem (CSP) on label set [ L ] . We show that, assuming the Unique Games Conjecture, it achieves an approximation within O ( k 3 log L ) of the optimal approximation factor. In particular we prove the following hardness result: let be a k -ary CSP on label set [ L ] with constraints from a constrain t clas s , such that it is a ( c s ) -integrality gap for the standard LP relaxation. Then, given an instance with constraints from , it is NP-hard to decide whether, opt ( ) c k 3 log L or opt ( ) 4 s assuming the Unique Games Conjecture. We also show the existence of an efficient LP rounding algorithm Roun d such that a lower bound for it can be translated into a similar (but weaker) hardness result. In particular, if there is an instance from a permutatio n invarian t constraint class which is a ( c s ) - roundin g ga p for Roun d , then given an instance with constraints from , it is NP-hard to decide whether, opt ( ) c k 3 log L or opt ( ) O ( log L ) k s assuming the Unique Games Conjecture.

An extended abstract of this paper appeared in the Proceedings of The 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015).