An explicit vector algorithm for high-girth MaxCut

Jessica K. Thompson, Ojas Parekh, Kunal Marwaha

We give an approximation algorithm for MaxCut and provide guarantees on the average fraction of edges cut on $d$-regular graphs of girth $\ge 2k$. For every $d\ge 3$ and $k \geq…