A Classical Algorithm Which Also Beats 1/2+2/π1/√(D) For High Girth MAX-CUT

11/24/2021

∙

by   Matthew B. Hastings, et al.

∙

0

∙

share

We give a simple classical algorithm which provably achieves the performance in the title. The algorithm is a simple modification of the Gaussian wave process.