These videos are THICK I usually watch lectures etc on 2x but I cannot do so for your videos I have to actually pause your videos and think about it, and it's great, thank you
SO cool! There are some other really interesting relationships between graph invariants and SDP, such as the Lovasz number of a graph. This number can be solved as an SDP and it bounds the Shannon capacity, clique number, and chromatic number (the latter 2 are NP hard to compute, and the Shannon capacity’s complexity is unknown)
Amazing video and an awesome series! The connection between Semi definite programming and the Unique games conjuncture goes even further. If the UGC is true, then every constraint satisfaction problem has a Semi definite program that gives the optimal approximation ratio (assuming P!=NP)
3:39 It's possible to get less than 1/2 Max-Cut. If all nodes are the same color, that's 0 cuts. We would have to shuffle the list of nodes and split them equally for assignment. Independent assignments will get you something like coin-flip results without a 1/2 lower bound.
Awesome videos! Really enjoying the brevity and animations. A note: it is *really* hard to see the blue vs red nodes for me due to colorblindness. It would be better in my particular case to have deeper hues, or more value (light/dark) separation. Thought I'd mention cause I find it goes unnoticed often until someone shares about it! Going to go back and watch the rest of the series now :D
description of the problem was too fast for a while I could not understand why not to color everything in one color to get zero - the minimum value - and where exactly the restriction, like "divide in equal amounts", comes in...
Thanks for watching! There is no restriction, you can absolutely color everything with the same color. But that would lead to a cut of value zero, which is the minimum value as you correctly pointed out. In a max-cut problem we want the _maximum_ value though, so you always want to fully use both colors.
@@dmit10 Great question! If X were rank one, we would solve the Max-Cut problem exactly! (which would be amazing :-) ). We have no practical way of enforcing that when we write our SDP, and this is the main reason it is only a relaxation (and not an exact reformulation of the problem). To answer your question more directly, at 4:58, when we take the square root of the matrix X, we do not need X to be of rank 1.
Beautiful explanation and graphics. Couldn't help add this aside -- the rounding procedure use here also forms the basis of the apprx-near-neighbor data structures using locality sensitive hashing. Looking forward to watching the other videos. Is it possible to let us know what tools you use to create this? As mentioned below in one of the comments, anything about sum of squares would be awesome.
I love this series. Really clear. In this max cut application, I was half expecting you to come back to the choice of random hyperplane. In practice is that choice usually finessed in some way?
Your question has a fascinating answer depending on whether you believe the UGC (Unique game conjecture) is true or not. If UGC is true, then there is no way to improve on the completely random choice of that hyperplane (even repeating the sampling of this hyperplane and picking the best one won’t help). In fact, there would be no way to improve on the 87% of the G&W method that I presented in the video (unless p=np). If the ugc is false, then all bets are off…
@@VisuallyExplained If UGC is false but P e NP is true then for positively weighted adjacency matrices the approximation ratio is 16/17 [J. Håstad, J. ACM 48 (2001) 798-859].
A little bit lost in 8:47, could anyone please explain the last inequality at 8:47, why (1 - ) / 2 summing over all edges, is bigger or equal to max-cut value?
That’s because that sum is (by definition) the optimal value of the semidefinite program that was introduced earlier. And thay SDP was itself a relaxation of maxcut, meaning an optimization where we expanded the feasible region . So naturally, the SDP will attain a bigger or equal value to maxcut
It would be amazing if you could say something about scalable SDPs. You say there are efficient Algorithms, but this is not actually true. Only quite small instances of general SDPs can be solved in practice.
These videos are THICK
I usually watch lectures etc on 2x but I cannot do so for your videos
I have to actually pause your videos and think about it, and it's great, thank you
SO cool! There are some other really interesting relationships between graph invariants and SDP, such as the Lovasz number of a graph. This number can be solved as an SDP and it bounds the Shannon capacity, clique number, and chromatic number (the latter 2 are NP hard to compute, and the Shannon capacity’s complexity is unknown)
Amazing video and an awesome series! The connection between Semi definite programming and the Unique games conjuncture goes even further. If the UGC is true, then every constraint satisfaction problem has a Semi definite program that gives the optimal approximation ratio (assuming P!=NP)
Isn’t that absolutely fascinating?
this is sucha good video! It is concise, short, but treats the problems in depth, gives you a lot of insight. Keep up the marvelous work!
Much appreciated!
Very useful! Helped a lot in my work, because I was not able to catch classical algorithms for MAX-CUT problem using original papers. Subscribed.
3:39 It's possible to get less than 1/2 Max-Cut. If all nodes are the same color, that's 0 cuts. We would have to shuffle the list of nodes and split them equally for assignment. Independent assignments will get you something like coin-flip results without a 1/2 lower bound.
Amazing content! I'm shocked that you only have < 10k subscriber. Your channel deserve more audience
Maybe one day! :-)
Awesome videos!! Thanks for shining light on this cool topic
Nice, brief and clear, thank you so much!
Awesome videos! Really enjoying the brevity and animations. A note: it is *really* hard to see the blue vs red nodes for me due to colorblindness. It would be better in my particular case to have deeper hues, or more value (light/dark) separation. Thought I'd mention cause I find it goes unnoticed often until someone shares about it! Going to go back and watch the rest of the series now :D
Noted, thanks for letting me know! I'll pick colors with better contrast next time!
Cool! Above I should have said "deeper saturation" not hue, but I think you got it XD
Great Explanation!
As always amazing !! Thank you very much for the wonderful content.
This is awesome! Thanks for the series
Quality content. Mad effort!
Constraint satisfaction problems. So cool :)
Thanks, that’s very good material.
Thank you so much can you do something on sum of square programming :)
Great series !
I like your funny words magic man
I couldn't understand, why can't the max cut go through the edge (3,4) in the solution that we got at 6:40
description of the problem was too fast
for a while I could not understand why not to color everything in one color to get zero - the minimum value - and where exactly the restriction, like "divide in equal amounts", comes in...
Thanks for watching! There is no restriction, you can absolutely color everything with the same color. But that would lead to a cut of value zero, which is the minimum value as you correctly pointed out. In a max-cut problem we want the _maximum_ value though, so you always want to fully use both colors.
At 4:58 don't we imply that X has rank 1? It's not so automatically after solving an SDP.
@@dmit10 Great question! If X were rank one, we would solve the Max-Cut problem exactly! (which would be amazing :-) ). We have no practical way of enforcing that when we write our SDP, and this is the main reason it is only a relaxation (and not an exact reformulation of the problem).
To answer your question more directly, at 4:58, when we take the square root of the matrix X, we do not need X to be of rank 1.
Great video!!
Beautiful explanation and graphics. Couldn't help add this aside -- the rounding procedure use here also forms the basis of the apprx-near-neighbor data structures using locality sensitive hashing. Looking forward to watching the other videos. Is it possible to let us know what tools you use to create this? As mentioned below in one of the comments, anything about sum of squares would be awesome.
I see that you have answer the tools question elsewhere. Thanks again.
I am sorry but why do we want the big X matrix to be positive semidefinite ?
I love this series. Really clear.
In this max cut application, I was half expecting you to come back to the choice of random hyperplane. In practice is that choice usually finessed in some way?
Your question has a fascinating answer depending on whether you believe the UGC (Unique game conjecture) is true or not. If UGC is true, then there is no way to improve on the completely random choice of that hyperplane (even repeating the sampling of this hyperplane and picking the best one won’t help). In fact, there would be no
way to improve on the 87% of the G&W method that I presented in the video (unless p=np).
If the ugc is false, then all bets are off…
@@VisuallyExplained If UGC is false but P
e NP is true then for positively weighted adjacency matrices the approximation ratio is 16/17 [J. Håstad, J. ACM 48 (2001) 798-859].
A little bit lost in 8:47, could anyone please explain the last inequality at 8:47, why (1 - ) / 2 summing over all edges, is bigger or equal to max-cut value?
That’s because that sum is (by definition) the optimal value of the semidefinite program that was introduced earlier. And thay SDP was itself a relaxation of maxcut, meaning an optimization where we expanded the feasible region . So naturally, the SDP will attain a bigger or equal value to maxcut
I love your contents. It would be really helpful if you could show how you make these visualizations through blender and python manim. Thanks a lot
I will definitely make a video about that at some point
It would be amazing if you could say something about scalable SDPs. You say there are efficient Algorithms, but this is not actually true. Only quite small instances of general SDPs can be solved in practice.
Hi, Can I ask some questions?