# Using semidefinite programming for Inference — case of robust community detection.

Date: November 14, 2019
Time: 2:00 pm
Room: DBH 4011
A regular stochastic block model (RSBM) is a random graph model wherein the vertices are partitioned into $k$ communities, and a random regular graph is sampled conditioned on a prescribed number of edges between the communities. For example, if we sample a graph with no edges within communities, we obtain a model for sampling $k$-colorable graphs.  The Kesten-Stigum (KS) threshold is widely conjectured to mark a computational threshold for the problem of community detection for both RSBMs and general (irregular) SBMs.
1. For every $\epsilon$, there exists $m \in \N$ such that the $m^{th}$ level of the SDP hierarchy can detect communities in a dissortative RSBM which is $\epsilon$-above the KS threshold
2. The resulting SDP based algorithm is robust to $o(n)$-perturbations of the graph.