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)

@VisuallyExplained

2 жыл бұрын

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!

@VisuallyExplained

2 жыл бұрын

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.

As always amazing !! Thank you very much for the wonderful content.

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!! Thanks for shining light on this cool topic

Amazing content! I'm shocked that you only have < 10k subscriber. Your channel deserve more audience

@VisuallyExplained

2 жыл бұрын

Maybe one day! :-)

This is awesome! Thanks for the series

Nice, brief and clear, thank you so much!

Quality content. Mad effort!

Thanks, that’s very good material.

Great series !

Great Explanation!

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

@VisuallyExplained

2 жыл бұрын

Noted, thanks for letting me know! I'll pick colors with better contrast next time!

@oncedidactic

2 жыл бұрын

Cool! Above I should have said "deeper saturation" not hue, but I think you got it XD

Great video!!

Thank you so much can you do something on sum of square programming :)

Constraint satisfaction problems. So cool :)

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.

@anirbandasguptaIITGN

2 жыл бұрын

I see that you have answer the tools question elsewhere. Thanks again.

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?

@VisuallyExplained

2 жыл бұрын

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…

@mishaerementchouk

2 жыл бұрын

@@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].

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

@VisuallyExplained

2 жыл бұрын

I will definitely make a video about that at some point

I like your funny words magic man

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...

@VisuallyExplained

2 жыл бұрын

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

2 жыл бұрын

At 4:58 don't we imply that X has rank 1? It's not so automatically after solving an SDP.

@VisuallyExplained

2 жыл бұрын

@@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.

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

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?

@VisuallyExplained

2 ай бұрын

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 am sorry but why do we want the big X matrix to be positive semidefinite ?

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?