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}$?

  • 1
    $\begingroup$ That is a scary idea :) $\endgroup$ Feb 6 '17 at 22:06
  • 1
    $\begingroup$ 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? $\endgroup$
    – Aryeh
    Feb 6 '17 at 22:15
  • 1
    $\begingroup$ 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. ftp.cs.nyu.edu/~khot/papers/UGCSurvey.pdf $\endgroup$ Feb 6 '17 at 22:50
  • 1
    $\begingroup$ 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." $\endgroup$ Feb 6 '17 at 22:59
  • 1
    $\begingroup$ But isn't an UG instance generically defined on an unweighted graph? $\endgroup$ Feb 6 '17 at 23:01

Your Answer

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

Browse other questions tagged or ask your own question.