Linear Programming and Community Detection 7: The LP Relaxation Fails w.h.p. in the Logarithmic-Degree SBMResearch Paper
The stochastic block model (SBM) is the standard benchmark for community detection: a random graph whose vertices are split into hidden communities, with denser connections inside a community than across. For two equal communities, the best possible estimator of the hidden partition is the minimum bisection problem, which is NP-hard in the worst case. Its…