Computer Science/Discrete Mathematics Seminar I

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 vertices are partitioned into k communities, and a graph is sampled conditional on a prescribed number of inter- and intra-community edges. The problem of detection, where we are to decide with high probability whether a graph was drawn from this model or the uniform distribution on regular graphs, is conjectured to undergo a computational phase transition at a point called the Kesten-Stigum (KS) threshold. We consider two models of random graphs namely the well-studied (irregular) stochastic block model and a distribution over random regular graphs we'll call the degree-regular block model (DRBM). For both these models, we show that sufficiently high constant levels of our hierarchy can perform detection arbitrarily close to the KS threshold and that our algorithm is robust to up to a linear number of adversarial edge perturbations. Furthermore, in the case of DRBM, we show that below the Kesten-Stigum threshold no constant level can do so. Joint work with Jess Banks (U.C.Berkeley) and Sidhanth Mohanty (U.C. Berkeley)