[MUSIC] In this section we are going to see a different type of relaxation for Maxcut. We have seen that the integer program, where we have one variable xij for every pair of vertices, is not good in the sense that its natural linear program of relaxation has an integrity gap of almost two. Is there a better relaxation than the linear program running relaxation? Let's see. We can think of this as placing vertices on the line. In fact we have two possibilities. Instead of 0 and 1, let's think of them just for a change, as- 1 and 1. So every vertex can be placed on the line either on the left side or on the right side of the origin -1 or 1. A partition of the vertices for I, vertex of vi is either placed on -1 or 1 and so, if we take any pair of vertices i and j the product vi vj is either minus one or one. And so, if we look at the quantity one minus vi vj divided by two, this quadratic polynomial has value one. i and j are placed on different sides. And 0 if they're on the same side. So what this means is that the objective is can be rewritten as the maximum over every edge ij of the weight of the edge x 1- vivj over 2. So, here's an equivalent formulation of our integer program. Vi is a real number for every i whose square is equal to 1, and subject to that, we want to maximize the weighted sum of [INAUDIBLE] of 1 minus vi vg over 2 with this, we have an expression of the max cut program with polynomials of degree 2. This is a polynomial of degree 2, ViVj. That is a polynomial of degree 2. Now, what can you do with this? How can we relax this? Here is a relaxation. We had vi, a real number. Let's go to higher dimensions. Instead of having vi be on the real line, let's allow it to be a vector in a dimensional space In high dimensional space. Then what happens? Then vi is no longer a real number but a vector. What can we say about vi squared? Replace the square by the dot product. Vi dot vi equals 1 for every i. In other words Vi is a unit length, vector, in high dimensional space. And then, what is the objective? Maximize the weight at sum of 1 minus z i dot product v j over 2. This was a representation of Maxcut. That is a relaxation where you replace real numbers by vectors in higher dimension. So that's a quadratic relaxation for Maxcut. Maximize the weighted sum of 1 minus vi or .vj over 2, such that vi is a unit vector. Because data product is a natural extension of the product in one dimension then this quadratic relaxation can only give you a better value. That is, the maximum over all these vectors, the value of a quadratic relaxation is greater than or equal to the unknown optimal value so this is what we are going to be working with. And now we will see how to solve this and what to do with the solution.