<p>My question is particularly about the set-up in section $8$ (``Analysis of the KV Max-Cut instances") of the paper, <a href="https://arxiv.org/pdf/1211.1958.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/1211.1958.pdf</a>. </p>

<ul>
<li><p>What they call the Khot-Vishnoi UG instance doesn't seem like a generic UG instance. Am I right? The UG instance that they are starting from (at least the one in the middle of page 24) seems to assume that the underlying graph of the UG instance is such that it has a non-negative weight valued in the interval $[0,1]$ associated to every edge. (And this is what allows them to have the probability interpretation!) But isn't this an extra structure assumed to be true than what UG would come with? </p></li>
<li><p>In the middle of page $25$ when they construct the Max-CUT instance from the UG instance in the last step it says, "Output the edge $(w_{u_1,x \circ \pi_1 },w_{u_2, x \circ \pi_2 })$ ". Is that a typo? There is nothing called $u_1$ and $u_2$ defined before. Should that be, $(w_{v_1,x \circ \pi_1 },w_{v_2, x \circ \pi_2 })$?  (...atleast with $v_1, v_2$ this would look closer to the last step of the PCP inner-verifier construction at the bottom of page $18$ in the original KKMO reduction, <a href="https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf." rel="nofollow noreferrer">https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf.</a>.) </p>

<p>This step when the construction of Max-CUT is described it again refers to this quantity called $\cal{E}$ which I guess is a probability distribution on the edges of the UG instance that they are assuming to be given. Or does any UG instance somehow implicitly come with this thing they call $\cal{E}$? </p></li>
</ul>

CC BY-SA 3.0
2017-02-06T22:03:10.113Z
Why not write to one of them?
Aryeh
CC BY-SA 3.0
2017-02-06T22:06:03.170Z
That is a scary idea :)
gradstudent
CC BY-SA 3.0
2017-02-06T22:15:48.173Z
Not at all -- a clear, brief, to-the-point questions will more often than not get an answer, in my experience. What have you got to lose?
Aryeh
CC BY-SA 3.0
2017-02-06T22:50:42.553Z
First bullet: they take a generic UG instance, defined on a weighted (bipartite) graph. The assumption that the weights add up to 1 is just normalization: you can take any instance and divide all weights by the sum. Actually, for UG you can set all weights to $1/|E|$. See e.g. http://ftp.cs.nyu.edu/~khot/papers/UGCSurvey.pdf
Sasho Nikolov
CC BY-SA 3.0
2017-02-06T22:59:06.700Z
Regarding the other bullet: I think this is a typo, and should be $v_1, v_2$. Regarding $\mathcal{E}$, they say on p. 24 that they "write $(u,v,\pi) \sim \mathcal{E}$ to denote that edge $(u,v)$ with permutation $\pi = \pi_{u,v}$ is chosen with probability equal to its edge weight."
Sasho Nikolov
CC BY-SA 3.0
2017-02-06T23:01:32.550Z
But isn't an UG instance generically defined on an unweighted graph?
gradstudent
CC BY-SA 3.0
2017-02-06T23:15:02.613Z
If the graph is unweighted, take $\cal E$ as the uniform distribution on the edges. Being able to reduce from weighted instances is only more general. The UGC survey also mentions that the weighted case is equivalent to the unweighted.
Sasho Nikolov
<cc.complexity-theory><np-hardness><unique-games-conjecture><sum-of-squares>
Some questions about the Ryan O'Donnel and Yuan Zhou's paper "Approximability and proof complexity"
gradstudent
# Some questions about the Ryan O'Donnel and Yuan Zhou's paper "Approximability and proof complexity"

(Asked by: username_0 on 2017-02-06)

My question is particularly about the set-up in section $8$ (``Analysis of the KV Max-Cut instances") of the paper, <https://arxiv.org/pdf/1211.1958.pdf>.

* What they call the Khot-Vishnoi UG instance doesn't seem like a generic UG instance. Am I right? The UG instance that they are starting from (at least the one in the middle of page 24) seems to assume that the underlying graph of the UG instance is such that it has a non-negative weight valued in the interval $[0,1]$ associated to every edge. (And this is what allows them to have the probability interpretation!) But isn't this an extra structure assumed to be true than what UG would come with?
* In the middle of page $25$ when they construct the Max-CUT instance from the UG instance in the last step it says, "Output the edge $(w\_{u\_1,x \circ \pi\_1 },w\_{u\_2, x \circ \pi\_2 })$ ". Is that a typo? There is nothing called $u\_1$ and $u\_2$ defined before. Should that be, $(w\_{v\_1,x \circ \pi\_1 },w\_{v\_2, x \circ \pi\_2 })$? (...atleast with $v\_1, v\_2$ this would look closer to the last step of the PCP inner-verifier construction at the bottom of page $18$ in the original KKMO reduction, <https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf.>.)

  This step when the construction of Max-CUT is described it again refers to this quantity called $\cal{E}$ which I guess is a probability distribution on the edges of the UG instance that they are assuming to be given. Or does any UG instance somehow implicitly come with this thing they call $\cal{E}$?

**Tags:** cc.complexity-theory, np-hardness, unique-games-conjecture, sum-of-squares

> **Comments:**
> **username_1**: Why not write to one of them?  
> **username_0**: That is a scary idea :)  
> **username_1**: Not at all -- a clear, brief, to-the-point questions will more often than not get an answer, in my experience. What have you got to lose?  
> **username_2**: First bullet: they take a generic UG instance, defined on a weighted (bipartite) graph. The assumption that the weights add up to 1 is just normalization: you can take any instance and divide all weights by the sum. Actually, for UG you can set all weights to $1/|E|$. See e.g. http://ftp.cs.nyu.edu/~khot/papers/UGCSurvey.pdf  
> **username_2**: Regarding the other bullet: I think this is a typo, and should be $v_1, v_2$. Regarding $\mathcal{E}$, they say on p. 24 that they "write $(u,v,\pi) \sim \mathcal{E}$ to denote that edge $(u,v)$ with permutation $\pi = \pi_{u,v}$ is chosen with probability equal to its edge weight."  
> **username_0**: But isn't an UG instance generically defined on an unweighted graph?  
> **username_2**: If the graph is unweighted, take $\cal E$ as the uniform distribution on the edges. Being able to reduce from weighted instances is only more general. The UGC survey also mentions that the weighted case is equivalent to the unweighted.  

---

## 0 answers

