Local Algorithms for Block Models with Side Information
Elchanan Mossel, Jiaming Xu · 2016
There has been a recent interest in understanding the power of local algorithms for optimization and inference problems on sparse graphs. Gamarnik and Sudan (2014) showed that local algorithms are weaker than global algorithms for finding large independent sets in sparse random regular graphs thus refuting a conjecture by Hatami, Lovász, and Szegedy (2012). Montanari (2015) showed that local algorithms are suboptimal for finding a community with high connectivityin the sparse Erdös-Rényi random graphs. For the symmetric planted partition problem (also named community detection for the block models) on sparse graphs, a simple observation is that local algorithms cannot have non-trivial performance.