Name
Abstract | ||
|---|---|---|
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 $\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. |
Year | Venue | Field |
|---|---|---|
2015 | Electronic Colloquium on Computational Complexity (ECCC) | Discrete mathematics,Combinatorics,Mathematical optimization,Local consistency,Constraint graph,Random assignment,Constraint satisfaction problem,Constraint satisfaction dual problem,Complexity of constraint satisfaction,Mathematics,Hybrid algorithm (constraint satisfaction),Bounded function |
DocType | Volume | Citations |
Journal | 22 | 6 |
PageRank | References | Authors |
0.64 | 6 | 10 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Boaz Barak | 1 | 2563 | 127.61 |
| Ankur Moitra | 2 | 892 | 56.19 |
| Ryan O'Donnell | 3 | 944 | 72.84 |
| Prasad Raghavendra | 4 | 1013 | 50.58 |
| Oded Regev | 5 | 2322 | 133.33 |
| David Steurer | 6 | 934 | 44.91 |
| Luca Trevisan | 7 | 2995 | 232.34 |
| Aravindan Vijayaraghavan | 8 | 179 | 16.59 |
| David Witmer | 9 | 78 | 4.33 |
| John Wright | 10 | 39 | 4.22 |