# How Well Do Local Algorithms Solve Semidefinite Programs?

arXiv: https://arxiv.org/abs/1610.05350 · HTML: https://mlsanity.com/paper/1610.05350/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2016.

## Built on by (most cited first, 2 of 2)

- [Streaming Belief Propagation for Community Detection](https://mlsanity.com/paper/2106.04805/) (2021)
- [A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of Random CSPs](https://mlsanity.com/paper/2204.10881/) (2022)

## Abstract (arXiv)

Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing --and yet poorly understood-- dichotomy. Either simple local algorithms succeed in estimating the object of interest, or even sophisticated semi-definite programming (SDP) relaxations fail. In order to explore this phenomenon, we study a classical SDP relaxation of the minimum graph bisection problem, when applied to ErdHos-Renyi random graphs with bounded average degree d>1, and obtain several types of results. First, we use a dual witness construction (using the so-called non-backtracking matrix of the graph) to upper bound the SDP value. Second, we prove that a simple local algorithm approximately solves the SDP to within a factor 2d2/(2d2+d-1) of the upper bound. In particular, the local algorithm is at most 8/9 suboptimal, and 1+O(1/d) suboptimal for large degree. We then analyze a more sophisticated local algorithm, which aggregates information according to the harmonic measure on the limiting Galton-Watson (GW) tree. The resulting lower bound is expressed in terms of the conductance of the GW tree and matches surprisingly well the empirically determined SDP values on large-scale ErdHos-Renyi graphs. We finally consider the planted partition model. In this case, purely local algorithms are known to fail, but they do succeed if a small amount of side information is available. Our results imply quantitative bounds on the threshold for partial recovery using SDP in this model.