A classic and popular statistical setting for evaluating between different solutions to this problem is the stochastic block model, also referred to as the planted partition model. In this talk, we present a new algorithm for this problem, which improves by polynomial factors over the performance of all previous known algorithms. It is based on convex optimization, and draws a connection between this problem and a different field: high-dimensional statistical inference.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.