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

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 -