Local algorithms for Maximum Cut and Minimum Bisection on locally treelike regular graphs of large degree

Given a graph $G$ of degree $k$ over $n$ vertices, we consider the problem of computing a near maximum cut or a near minimum bisection in polynomial time. For graphs of girth $2L$, we develop a local message passing algorithm whose complexity is $O(nkL)$, and that achieves near optimal cut values among all $L$-local algorithms. Focusing on max-cut, the algorithm constructs a cut of value $nk\mathrm{/}4+n{\mathsf{P}}_{\star }\sqrt{k\mathrm{/}4}+\mathsf{e}\mathsf{r}\mathsf{r}(n,k,L)$, where ${\mathsf{P}}_{\star }\approx 0.763166$ is the value of the Parisi formula from spin glass theory, and $\mathsf{e}\mathsf{r}\mathsf{r}(n,k,L)=o_n(n)+n{o}_k(\sqrt{k})+n\sqrt{k}{o}_L(1)$ (subscripts indicate the asymptotic variables). Our result generalizes to locally treelike graphs, i.e., graphs whose girth becomes $2L$ after removing a small fraction of vertices. Earlier work established that, for random $k$-regular graphs, the typical max-cut value is $nk\mathrm{/}4+n{\mathsf{P}}_{\star }\sqrt{k\mathrm{/}4}+o_n(n)+n{o}_k(\sqrt{k})$. Therefore our algorithm is nearly optimal on such graphs. An immediate corollary of this result is that random regular graphs have nearly minimum max-cut, and nearly maximum min-bisection among all regular locally treelike graphs. This can be viewed as a combinatorial version of the near-Ramanujan property of random regular graphs.