MIT 6.854 Spring 2016 Lecture 21: Planted Clique and Random Matrix Theory

[@aleksagordic9593]

3:55 - 9:00 Erdos-Reyni random graph model 9:00 - 9:40 important fact 9:40 - 17:15 planted clique model and quasi-polynomial time algorithms 17:15 - 27:40 polynomial time algorithms for finding PC 27:40 theorem [AKS] - bound for k is ~sqrt(n), random matrix theory 32:50 - 39:20 step #1 39:20 - 52:15 step #2 55:09 very bad sound, low pass filter applied :(

[@thomas49th]

what does he say at 5:07 "so we think of it as an unordered ______ " ???

[@aleksagordic9593]

pair (i,j). So the world simplest ...