Beating the random assignment on constraint satisfaction problems of bounded degree

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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 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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 18th International Workshop, APPROX 2015, and 19th International Workshop, RANDOM 2015
EditorsNaveen Garg, Klaus Jansen, Anup Rao, Jose D. P. Rolim
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages110-123
Number of pages14
ISBN (Electronic)9783939897897
DOIs
StatePublished - Aug 1 2015
Event18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015 - Princeton, United States
Duration: Aug 24 2015Aug 26 2015

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume40
ISSN (Print)1868-8969

Other

Other18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2015, and 19th International Workshop on Randomization and Computation, RANDOM 2015
CountryUnited States
CityPrinceton
Period8/24/158/26/15

Keywords

  • Advantage over random
  • Bounded degree
  • Constraint satisfaction problems

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Beating the random assignment on constraint satisfaction problems of bounded degree'. Together they form a unique fingerprint.

Cite this