6
$\begingroup$

What is the critical step where things go wrong if one attempts to use Dinur's proof the PCP theorem to prove the unique games conjecture by starting from a unique label cover instance and doing gap amplification / alphabet reduction while preserving the fact that the problem is a unique label cover instance?

Obviously, the proof still holding essentially unchanged would contradict the fact that we know there is a subexponential time algorithm for unique games, unless all of NP has subexponential time algorithms. However, I'm trying to explicitly understand the critical step where the argument fails.

Since I'm trying to understand to the heart of the issue, I'd prefer to disregard "minor" technical assumptions like ensuring the graph is d-regular, an expander, etc. unless those are actually the main thing preventing the proof from going through.

$\endgroup$
  • 4
    $\begingroup$ I'm confused about the starting point. Label cover is NP-hard to decide, and then you can gap amplify to get the PCP theorem (so you reduce label cover to the gap version). But unique label cover (without gap) is solvable is in P to begin with, and it seems a no go even there. $\endgroup$ – Mahdi Cheraghchi Nov 21 at 4:17
8
$\begingroup$

The powering step fails. After the powering, each vertex is labeled with a neighborhood of the original graph. each edge checks that its endpoints agree on the intersection of their neighborhoods, and that this labeling satisfies the edges in this intersection. However, the edge cannot check anything about part of the labeling that lies outside the intersection of the neighborhoods, and therefore cannot enforce the uniqueness property.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.