Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
8 votes

Why does Dinur's proof of the PCP theorem fail to work for unique games?

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 ...
Or Meir's user avatar
  • 5,615
4 votes
Accepted

Proof of Majority is stablest in "reverse" in the MAXCUT hardness paper by Khot et al

"So, applying MIS on $g$" To apply the Majority is Stablest theorem, you need to apply it to a non-negative parameter $\rho'\in[0,1)$ (read the statement of the theorem). Since in Proposition 7.3 the ...
Clement C.'s user avatar
  • 4,471
1 vote

Minimization version of matrix p-norms?

Suppose that $A$ is an $m\times n$ matrix, and let $\mathcal{A}$ be the corresponding linear operator whose matrix (w.r.t. the standard basis) is $A$. Let $W\subseteq \mathbb{R}^m$ be the span of the ...
Sasho Nikolov's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible