  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 synchronization. Specifically, we are given directed
distances on a circle (i.e., directed angles) between pairs of elements and our
goal is to assign the elements to positions on a circle so as to preserve these
distances as much as possible. The feasibility of our rounding scheme is based
on properties of the well-known stochastic process called Brownian motion.
Based on computational and other evidence, we conjecture that this rounding
scheme yields an approximation guarantee that is very close to the
best-possible guarantee (assuming the Unique-Games Conjecture).

Data Structures and Algorithms