Theoretical Computer Science
cc.complexity-theory pcp unique-games-conjecture
Updated Fri, 24 Jun 2022 19:47:55 GMT

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

how can one show that what is relation between "Unique games conjecture" and "PCP theorem"? how does one explain "Unique games conjecture" is stronger form of "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.