Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable oc...

Full description

Bibliographic Details
Main Authors: Barak, Boaz, O'Donnell, Ryan, Raghavendra, Prasad, Regev, Oded, Steurer, David, Trevisan, Luca, Vijayaraghavan, Aravindan, Witmer, David, Wright, John, Moitra, Ankur
Other Authors: Massachusetts Institute of Technology. Department of Mathematics
Format: Article
Language:en_US
Published: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik 2016
Online Access:http://hdl.handle.net/1721.1/104772
https://orcid.org/0000-0001-7047-0495

Internet

http://hdl.handle.net/1721.1/104772
https://orcid.org/0000-0001-7047-0495

Similar Items