Last week I gave a talk at the CISS 2014 conference here in Princeton about a new paper with Emmanuel Abbe, Annina Bracher, and Amit Singer. I thought it would be an excellent opportunity to talk about this problem in the blog.
The problem is very simple, given a graph and unknown Boolean variables on the vertices we observe edge-variables given by, for ,
where are iid random noise terms satisfying
The objective is to recover the value of the vertex variables , up to a global flip. This problem is also known as Synchronization (in fact, I talked about it before in this blog), and it can also be seen as particular instance of community detection. We are interesting in exact recovery of , with high probability.
For simplicity we’ll start considering the case on which is an s R\’ is showing that, as long as,
Remarkably, the condition (1) is essentially tight as we can show that, as long as then, for
exact recovery is hopeless.
Unfortunately, the maximum likelihood estimator is, in general, NP-hard to compute. As a tractable alternative we propose an approach based in Semidefinite Programming. I have explained how this algorithm works in a past post. Using tools similar to the ones explained previously here we were able to show that, while condition (1) is not sufficient for the SDP approach to give exact recovery, as long as
This raises, in my opinion, an extremely interesting question: Is there any polynomial time algorithm that can match the threshold of the maximum likelihood estimator or is it the fact that there is a complexity gap and below a certain threshold (different than (1)) there is no poly-time algorithm that can achieve exact recovery?