Great video! I got a little confused at the LP-SAT proof part when you were talking about Jensen's inequality and concave functions. I'm pretty sure the function shown at 7:17 is a convex function. I think the inequality is the other way around, i.e. f(x) >= a + bx if f concave on [0,1]. Only then can you substitute the bound at 8:10.
As a computer science and mathematics major, this content really hits the niche intersection I'm interested in. Thank you for this high-level content that you've somehow made easier than expected to digest.
Fun fact: if every clause uses exactly 3 distinct variables, RAND-SAT gives us 7/8 of the optimum in expectation (actually 7/8 of all clauses), but approximating this case to anything higher than 7/8 of the optimum is NP-complete
what does it mean to choose one or the other algorithm for each clause independently? The algorightms work on whole expression, and the clauses share variables. I am confused. Also, not easy to find references of BEST SAT online
You can go clause by clause and, for each one, use the algorithms to assign the values of the variables (that haven't been assigned yet). If RAND-SAT were chosen for the clause, you would look at each unassigned variable in the clause and flip a coin, setting it to True/False accordingly. If LP-SAT were chosen, you would again look at each unassigned variable, and assign it True/False based on the value that the relaxed linear program suggests.
Both algorithms give you a probability distribution for each variable (rand gives you 50% true 50% false and lp gives you the probability from the value of the variable in the linear program). So for each variable flip a coin, if it's heads flip a fair coin (use rand) to decide between true and false. If it's tails flip a biased coin (use lp) to decide. Hope this helps
If you breathed for like 5 seconds at the start to leave me enough time to turn the volume up without missing half the premise of the full video it would be great :)))
When a clause has more variables, the chance that the algorithm randomly picks one to be satisfied (which is 50%) and thus satisfying the entire clause is larger.
Great video! I got a little confused at the LP-SAT proof part when you were talking about Jensen's inequality and concave functions. I'm pretty sure the function shown at 7:17 is a convex function. I think the inequality is the other way around, i.e. f(x) >= a + bx if f concave on [0,1]. Only then can you substitute the bound at 8:10.
Yikes, you're right. Thanks for the comment, both the function and the inequality should be flipped.
As a computer science and mathematics major, this content really hits the niche intersection I'm interested in. Thank you for this high-level content that you've somehow made easier than expected to digest.
Fun fact: if every clause uses exactly 3 distinct variables, RAND-SAT gives us 7/8 of the optimum in expectation (actually 7/8 of all clauses), but approximating this case to anything higher than 7/8 of the optimum is NP-complete
Yes, another underrated youtube channel. We love those youtube :)
pěkné
Suggestion: boost your volume. It is wildly lower than other yt vids
PS - thank you for your videos! I always learn something
what does it mean to choose one or the other algorithm for each clause independently? The algorightms work on whole expression, and the clauses share variables. I am confused. Also, not easy to find references of BEST SAT online
You can go clause by clause and, for each one, use the algorithms to assign the values of the variables (that haven't been assigned yet).
If RAND-SAT were chosen for the clause, you would look at each unassigned variable in the clause and flip a coin, setting it to True/False accordingly.
If LP-SAT were chosen, you would again look at each unassigned variable, and assign it True/False based on the value that the relaxed linear program suggests.
fix the volume plz.....
Can't we just model the factories problem with a bipartite graph and solve for max-match in linear time ?
I didn't understand what it means to average LP SAT with random SAT, how is BEST sat defined?
For each clause, you independently flip a coin and decide to use either LP-SAT or RAND-SAT.
Both algorithms give you a probability distribution for each variable (rand gives you 50% true 50% false and lp gives you the probability from the value of the variable in the linear program). So for each variable flip a coin, if it's heads flip a fair coin (use rand) to decide between true and false. If it's tails flip a biased coin (use lp) to decide. Hope this helps
If you breathed for like 5 seconds at the start to leave me enough time to turn the volume up without missing half the premise of the full video it would be great :)))
your mic is too low
i truly cannot understand a thing rise the volume
@@itellyouforfree7238 ill just have to w8 until your society is full of blacks ... i just need to w8 to have satisfaction
He should reupload with higher volume. So much work put into it and then spoiled by a little fixable mistake
I don't understand why RAND-SAT gets better as the number of variables increases…
When a clause has more variables, the chance that the algorithm randomly picks one to be satisfied (which is 50%) and thus satisfying the entire clause is larger.