Beating the random assignment on constraint satisfaction problems of bounded degree
with Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright. APPROX 2015.
abstract
We show that for any odd and any instance of the MAX -LIN constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a fraction of ’s constraints, where is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a fraction of the equations.
For arbitrary constraint satisfaction problems, we give a similar result for “triangle-free” instances; i.e., an efficient algorithm that finds an assignment satisfying at least a fraction of constraints, where is the fraction that would be satisfied by a uniformly random assignment.