28 citations · 130 across the 32 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2015★ 8 cited
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 and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…
cs.CC2011★ 1 cited
On Quadratic Programming with a Ratio Objective
Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran +1
Quadratic Programming (QP) is the well-studied problem of maximizing over {-1,1} values the quadratic form \sum_{i \ne j} a_{ij} x_i x_j. QP captures many known combinatorial optim…