<p>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.</p>

CC BY-SA 4.0
2020-11-20T22:10:56.890Z
2020-11-20T22:10:56.890Z
Or Meir
<p>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?</p>
<p>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.</p>
<p>Since I'm trying to understand to the heart of the issue, I'd prefer to disregard &quot;minor&quot; 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.</p>

CC BY-SA 4.0
2020-11-21T04:17:53.363Z
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.
Mahdi Cheraghchi
<cc.complexity-theory><np-hardness><approximation-hardness><pcp><unique-games-conjecture>
Why does Dinur's proof of the PCP theorem fail to work for unique games?
user
# Why does Dinur's proof of the PCP theorem fail to work for unique games?

(Asked by: username_0 on 2020-11-19)

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.

**Tags:** cc.complexity-theory, np-hardness, approximation-hardness, pcp, unique-games-conjecture
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2020-11-20. Score: 10

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.


---

