1
$\begingroup$

If there is a variable $x_i$ for every vertex $i$ of a $d$-regular graph $G$ then assigning $x_i = \pm 1$ gives a cut, say $(S,\bar{S})$, of the graph. We can then see that, $\langle x,L x\rangle$, where $L = I - A/d$, equals $4E(S,\bar{S})/d$. So trying to maximize $\langle x,Lx \rangle$ over $x \in \{1,-1\}^{|V|}$ maximizes the number of edges crossing across the cut, $(S,\bar{S})$.

With this set-up the Goemans–Williamson algorithm is stated in the sum-of-squares (SOS) literature as the claim that there exists a polynomial-time algorithm such that one can output a vector $z \in \{ \pm 1 \}^{\vert V \vert }$ such that $\langle z,Lz \rangle \geq 2n(1-f_{GW}(\epsilon))$ where $f_{GW}(\epsilon) \leq 10\sqrt{\epsilon}$ provided one is given a degree-2 pseudo-distribution such that $\tilde {\mathbb{E}} [x_i ^2] =1, \tilde {\mathbb{E}} [\langle x, Lx \rangle ] \geq 2n(1-\epsilon)$

So naturally the question arises as to from where does one get such a degree-2 pseudo-distribution? The implicit claim seems to be that there exists a "degree-2 SOS algorithm" which when run on these constraints $\{ x_i^2 =1, \langle x, Lx\rangle = 2n(1-\epsilon)\}$ will generate this "degree-2 pseudo-distribution". This apparently seems to be set up to be a semidefinite programming (SDP) question and hence one basically has to solve a SDP to get this pseudo-distribution!

  • So what is the advantage of the SOS point of view here if one has to anyway run a SDP to get this degree-2 pseudo distribution?
  • Also can someone point out an explicit reference about what exactly is this "degree-2 SOS algorithm" which will run on these constraints to give me the "degree-2 pseudo-distribution"?
Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ There is no computational benefit of thinking of Goemans-Willimsion in this way, the point is rather that Goemans-Williamson is a useful example of using the SoS framework for an approximation problem. As for the algorithm, Definition 1.4. from Barak's notes defines the degree $d$ SoS algorithm (it's an easy exercise to formulate it as an SDP), and, as stated at the bottom of page 16, the bilinear form $M$ is the pseudoexpectation operator. $\endgroup$
    – Sasho Nikolov
    Mar 30, 2015 at 2:49
  • $\begingroup$ Thanks! Can you may be help translate this formulation into the usual $0.878$ framework? I am hard presed to recover that famous number from this $\epsilon$ statement! What is the connection? $\endgroup$
    – user6818
    Mar 30, 2015 at 3:08
  • 1
    $\begingroup$ I don't think that the version of Goemans-Williamson you give implies the $0.878$ constant. Both follow from the same analysis though. There is absolutely no difference in how GW is analyzed here, the only observation is that one can express in "SoS language". $\endgroup$
    – Sasho Nikolov
    Mar 30, 2015 at 5:22
  • 2
    $\begingroup$ Here is how: take the pseudodistribution that optimizes $\tilde{\mathbb{E}}[\langle x, Lx\rangle]$ subject to $\tilde{\mathbb{E}}[x_i^2]= 1$. Sample an $n$-dim Gaussian $g$ with mean 0 and covariance matrix $C$, $c_{ij} = \tilde{\mathbb{E}}[x_i x_j]$. Set $z_{i} = \mathrm{sign}(G_i)$. You can show $\mathbb{E}[\langle z, Lz, \rangle] \geq 0.878\tilde{\mathbb{E}}[\langle x, Lx \rangle]$ exactly as in Goemans-Williamson. $\endgroup$
    – Sasho Nikolov
    Mar 30, 2015 at 5:22
  • 1
    $\begingroup$ Just posted an answer. In my comments I didn't work out that 0.878 constant, but as Sasho says one can use Goemans-Williamson's analysis as is to derive it. $\endgroup$
    – Boaz Barak
    Mar 31, 2015 at 4:32

1 Answer 1

Reset to default
7
$\begingroup$

Looking at the Goemans–Williamson algorithm in the SOS framework yields no technical advantages: it is exactly the same algorithm and the same ideas are used in the analysis. The only advantages in doing so are:

  1. Arguably the algorithm seems less "magical" in that viewpoint, though of course that's a matter of taste.
  2. It's a good basic case to get intuition for the SOS framework, and so understanding this algorithm will help in understanding more complicated uses of it.

As Sasho Nikolov points out, a degree 2 pseudo-distribution is simply a positive semidefinite (PSD) matrix, and so finding such a matrix satisfying any particular linear constraints can be done via semidefinite programming. In particular, for any pseudo-distribution $\{ u_i \}_i$ of degree at least 2, the matrix $X_{i,j} = \tilde{\mathbb{E}} u_i u_j$ is PSD.

Given an $n\times n$ PSD matrix $X$, one can find a Gaussian distribution $y\in\mathbb{R}^n$ such that $\mathbb{E} y_iy_j = X_{i,j}$ for all $i,j$ and hence the distribution $\{ y_i \}_i$ matches the second moments of the pseudo-distribution represented by $X$. (One can obtain $y$ by sampling a standard Gaussian vector $z$ and letting $y=X^{1/2}z$.)

The rounding algorithm is to obtain a distribution $w$ over $\{\pm 1\}^n$ by letting $w_i = \textrm{sign}(y_i)$. This is exactly equivalent to the standard description of "hyperplane rounding" whereas one takes vectors $v_1,\ldots,v_n$ such that $X_{i,j} = \langle v_i,v_j \rangle$ and lets $w_i = \textrm{sign}(\langle v_i , z\rangle)$ where $z$ is a random Gaussian vector.

Now we want to compare the value of the pseudo-distribution, which (up to scaling) is the same as the sum of $-X_{i,j}$ over all edges $(i,j)$, with the expected value of our rounded solution $w$, which will be the sum of $- w_iw_j$. So now we want to calculate the probability that the edge will be cut by $w$ as a function of $X_{i,j}$. It all boils down to figuring out the following calculation: if $w_i$ and $w_j$ are two Gaussian random variables with $\mathbb{E} w_i^2 = \mathbb{E} w_j^2 = 1$ and $\mathbb{E} w_i w_j = \rho$, what would be the probability that their signs agree? I personally think that the most interesting regime for Max-Cut is when the objective value is close to $1$. One nice thing in that regime is that you can get some qualitative insight by showing that if $\rho = -1 +\epsilon$ then their signs agree with probability at most $O(\sqrt{\epsilon})$. However, if you are interested in figuring out the approximation ratio (or more generally figure out the precise trigonometric function behind this $O(\cdot)$ term) then Goemans–Williamson's analysis exactly resolves this calculation.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @Boasz Barak Is there anything more to be gained by using a higher than 2 degree pseudo-distribution here? $\endgroup$
    – Student
    Mar 31, 2015 at 17:19
  • 3
    $\begingroup$ That's a very interesting open question... (am interpreting it as whether the maximum ratio between the true value and the relaxation value improves for degree larger than 2). Obviously degree $O(n)$ pseudo-distribution will solve Max-Cut exactly. It is believed, but not proved, that like unique games, it should be possible to get a constant improvement over the approximation factor using only degree $n^{\epsilon}$ for some $\epsilon<1$. If the unique games conjecture is true then this cannot be done with degree $n^{o(1)}$ but we don't even know what happens for degree $4$. $\endgroup$
    – Boaz Barak
    Apr 1, 2015 at 1:01
  • $\begingroup$ @BoaszBarak Thanks! To compare this (1) The proof in your notes that the hypercube is a small-set expander goes through a 2-4 hypercontractivity inequality. If one could rewrite that proof via a 2-(q>4) hypercontractivity inequality then would it be equivalent to finding a higher degree SOS proof of the small-set expander property of the hypercube? And will it have any advantages? (2) In that same hypercontractivity inequality does anything depend on the "d" (one that occurs in the upperbound as 9^d)? Does the choice of d measure any complexity ? $\endgroup$
    – Student
    Apr 1, 2015 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.