The Unique Games Conjecture (UGC) has pinned down the approximability of all constraint satisfaction problems (CSPs), showing that a natural semidefinite programming relaxation offers the optimal worst-case approximation ratio for any CSP. This elegant picture, however, does not apply for CSP instances that are perfectly satisfiable, due to the imperfect completeness inherent in the UGC. For the important case when the input CSP instance admits a satisfying assignment, in general it remains wide open to understand how well it can be approximated.

This work is motivated by the pursuit of a better understanding of the inapproximability of perfectly satisfiable instances of CSPs. Our main conceptual contribution is the formulation of a (hypergraph) version of Label Cover which we call ``V label cover.'' Assuming a conjecture concerning the inapproximability of V label cover on perfectly satisfiable instances, we prove the following implications:

\begin{itemize} \item There is an absolute constant c 0 such that for k 3 , given a satisfiable instance of Boolean k -CSP, it is hard to find an assignment satisfying more than c 0 k 2 2 k fraction of the constraints.

\item Given a k -uniform hypergraph, k 2 , for all 0"> 0 , it is hard to tell if it is q -strongly colorable or has no independent set with an fraction of vertices, where q = k + k − 1 2 .

\item Given a k -uniform hypergraph, k 3 , for all 0"> 0 , it is hard to tell if it is ( k − 1 ) -rainbow colorable or has no independent set with an fraction of vertices. \end{itemize}

We further supplement the above results with a proof that an ``almost Unique'' version of Label Cover can be approximated within a constant factor on satisfiable instances.