ECCC-Report TR15-082https://eccc.weizmann.ac.il/report/2015/082Comments and Revisions published for TR15-082en-usWed, 13 May 2015 17:31:46 +0300
Paper TR15-082
| Beating the random assignment on constraint satisfaction problems of bounded degree |
Aravindan Vijayaraghavan,
Boaz Barak,
Ryan O'Donnell,
Ankur Moitra,
Prasad Raghavendra,
Oded Regev,
David Steurer,
Luca Trevisan,
David Witmer,
John Wright
https://eccc.weizmann.ac.il/report/2015/082We 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{1}{2} + \Omega(1/\sqrt{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 $\frac{1}{2} + \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 $\mu + \Omega(1/\sqrt{D})$ fraction of constraints, where $\mu$ is the fraction that would be satisfied by a uniformly random assignment.Wed, 13 May 2015 17:31:46 +0300https://eccc.weizmann.ac.il/report/2015/082