TY - GEN
T1 - Beating the random assignment on constraint satisfaction problems of bounded degree
AU - Barak, Boaz
AU - Moitra, Ankur
AU - O'Donnell, Ryan
AU - Raghavendra, Prasad
AU - Regev, Oded
AU - Steurer, David
AU - Trevisan, Luca
AU - Vijayaraghavan, Aravindan
AU - Witmer, David
AU - Wright, John
N1 - Publisher Copyright:
© Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright.
PY - 2015/8/1
Y1 - 2015/8/1
N2 - 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 1/2 +Ω (1/√ D) fraction of ß's 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 1/2 +Ω (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.
AB - 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 1/2 +Ω (1/√ D) fraction of ß's 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 1/2 +Ω (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.
KW - Advantage over random
KW - Bounded degree
KW - Constraint satisfaction problems
UR - http://www.scopus.com/inward/record.url?scp=84958520302&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958520302&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.APPROX-RANDOM.2015.110
DO - 10.4230/LIPIcs.APPROX-RANDOM.2015.110
M3 - Conference contribution
AN - SCOPUS:84958520302
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 110
EP - 123
BT - Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
A2 - Garg, Naveen
A2 - Jansen, Klaus
A2 - Rao, Anup
A2 - Rolim, Jose D. P.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
Y2 - 24 August 2015 through 26 August 2015
ER -