Beating the random assignment on constraint satisfaction problems of bounded degree

Boaz Barak, Ankur Moitra, Ryan O'Donnell +7

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…