



00984nas a2200133   4500008004100000245005500041210005100096260001400147520059000161100002600751700001700777700001900794856003700813       2021                        eng d00aAn explicit vector algorithm for high-girth MaxCut0 aexplicit vector algorithm for highgirth MaxCut  c8/27/20213 a<p>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&ge;4, our approximation guarantees are better than those of all other classical and quantum algorithms known to the authors. Our algorithm constructs an explicit vector solution to the standard semidefinite relaxation of MaxCut and applies hyperplane rounding. It may be viewed as a simplification of the previously best known technique, which approximates Gaussian wave processes on the infinite d-regular tree.</p>1 aThompson, Jessica, K.1 aParekh, Ojas1 aMarwaha, Kunal  uhttps://arxiv.org/abs/2108.12477