# Beating the random assignment on constraint satisfaction problems of bounded degree

arXiv: https://arxiv.org/abs/1505.03424 · HTML: https://mlsanity.com/paper/1505.03424/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2015.

## Built on by (most cited first, 2 of 2)

- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Classical State Preparation for Variational Quantum Algorithms via Reinforcement Learning](https://mlsanity.com/paper/2605.23138/) (2026)

## Abstract (arXiv)

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 frac12 + Omega(1/√D) fraction of constraints, where D 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 frac12 + Omega(D-3/4) 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 μ + Omega(1/√D) fraction of constraints, where μ is the fraction that would be satisfied by a uniformly random assignment.