[MUSIC] Let me tell you a few things about Max-Cut and this amazing famous Max-Cut algorithm. First, there are a few negative results about Max-Cut, unfortunately. You know this man at this point, Karp. You know this result, NP-completeness. You've seen these people before. Tap that image for you. I'll mention that paper of theirs, in fact, where they prove, among other things, that Max-Cut cannot be approximated to within 1 plus epsilon. This man, Johan Hastad, improved the bond a little bit. So, we know that there's no approximation scheme for Max-Cut in polynomial-time, SP's different from NP. sBut worst than that, worst than that if a certain conjunction hold, the Unique Games Conjecture, UGC, then it is NP-hard to find an approximation of Max-Cut better than 0.878. In other words, if the UGC holds, then this algorithm are presented to you for Max-Cut in the next section. Is the best you can hope for. It gives you the best possible approximation. Its simplicity is deceptive. It's the best you can do. This result is due to Subash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell. But what is this Unique Games Conjecture on which this result rests? It's a conjecture, it may or may not be true, we do not know. In fact, many people are not so convinced. It's that a particular problem we conjecture, maybe is NP-hard. See the question mark. What is this problem? The input is a graph. On every edge, you have a mapping from colors to colors. If you have an edge from U to V, the map says something like if U is green, then v must be red. If u is red, then v must be green. If u is blue, then v must be blue, and so on. It's a permutation from colors to colors by injection. So that the color of u determines the color of v. And so it's called an edge rule, an edge constraint. And we have the guarantee that the input is such that either there's a way to give a color to every vertex, to satisfy not 100% of the edge constraints, but at least 90%. Either it's possible to satisfy 90%, at least, of the edge constraints or it's totally impossible, that is, no coloring can satisfy more than 10% of the constraints. So, either it's possible to satisfy almost all of the constraints, or almost none. For example, here you are satisfying three of the four constraints. Red green is correct. Red red is correct. Red blue is correct. It satisfies these rules, but green red is not correct. According to this it should be green green. So, of these four edges, three are satisfied. That's the input. The output is to decide which of the two holds. To decide whether the input is almost all satisfiable or almost not at all. There's a big gap between the two. Okay, so that is an open question. That's the Unique Games Conjecture. Positive results, positive results. What do we have? The result we gave was built in three steps. First, we need the Ellipsoid method to be able to solve our vector program in polynomial-time. The Ellipsoid method was first designed by Leonid Khachiyan for linear programming. And then there were some developments in particular by Grotschel, Lovasz and Schrijver using it for SDPs. These three offers have something in common, if you look at their names. It's almost impossible to spell their last name correctly. For all of them. Look at those, all of them have different [INAUDIBLE] in their names. Aside from that, they wrote a book together where they developed the ellipsoid method for SDPs. Second step. Come up with this SDP relaxation for Max-Cut. This was done by Charles Delorme and Svatopluk Poljak and the observed eye that it's possible to solve this SDP relaxation in polynomial-time. Third step, is to come up with this very simple randomized rounding. And therefore, use this SDP relaxation for approximation algorithm. And obtain the 0.878 approximation. This is a very famous paper by Michel Goemans and David Williamson. So, that's the state of the art on the Max-Cut. Many other results exist on Max-Cut. Many variances have been studied but this is the central part of the research in this field.