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

Ahmed El Alaoui, Andrea Montanari, Mark Sellke

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$,…