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 2 1 + (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 \emph{quantum} algorithm to find an assignment satisfying a 2 1 + ( 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 + (1 D ) fraction of constraints, where is the fraction that would be satisfied by a uniformly random assignment.