Rounding semidefinite programs for large-domain problems via Brownian motion

Kevin L. Chang, Alantha Newman

We present a new simple method for rounding a semidefinite programming relaxation of a constraint satisfaction problem. We apply it to the problem of approximate angular synchroniz…