Is there a simple argument that shows that the unique games conjecture implies the PCP theorem

The related $2-1$-conjecture of Khot implies the PCP theorem with perfect completeness: The proof is expected to give a labeling of the vertices. The verifier selects a random edge queries its endpoints and accepts iff the constraint holds.

For getting a PCP theorem with perfect completeness from the unique games conjecture you need to, as Boaz writes, convert a $(c,s)$ PCP into one with perfect completeness. One way to do that is:

Add new variables one per constraint, and modify the constraint to be satisfied if either the new variable is true, or else if the constraint were previously satisfied. Now the question is reduced to finding a PCP for deciding if a set of m bits (=the new vars) has sum at most $(1-c)\cdot m$ or at least $(1-s)\cdot m$. This seems like a non-trivial question, but easier than the PCP theorem.

Solved by user8400 (206 )
Feb 14, 2012 at 17:20