Local Statistics, Semidefinite Programming, and Community Detection

Jess Banks, Sidhanth Mohanty, Prasad Raghavendra

We propose a new hierarchy of semidefinite programming relaxations for inference problems. As test cases, we consider the problem of community detection in block models. The vertic…