Computing Extremal Cuts in Locally Treelike Graphs

Computing Extremal Cuts in Locally Treelike Graphs (via Zoom)

Abstract: We consider the problem of efficiently computing a near maximum cut or a near minimum bisection of a regular graph of large girth. We develop an iterative local algorithm which, when given a k-regular graph of girth 2L, produces a cut with the following two extremal properties when k and L are large:

(1) The achieved cut value is approximately optimal among all L-local algorithms. 

(2) This value approximately matches the true 'ground state' value on random k-regular graphs.           

As a consequence, random regular graphs have approximately minimum max-cut value, and maximum min-bisection value among all locally-treelike regular graphs of the same degree. This can be seen as a combinatorial version of the near-Ramanujan property of random regular graphs. 

This is based on a joint work with Andrea Montanari and Mark Sellke. 

Bio: Ahmed El Alaoui is an assistant professor at the Department of Statistics and Data Sciences at Cornell University, since January 2021. Before joining Cornell, he was a postdoctoral researcher from 2018 to 2020 at Stanford University, hosted by Andrea Montanari. Ahmed received his PhD in 2018 in Electrical Engineering and Computer Sciences from UC Berkeley, under the supervision of Michael Jordan. His research interests revolve around high-dimensional statistics and probability theory, statistical physics, algorithms, and problems where these areas meet.