2026-07-20T05:35:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5298 2024-03-06T10:36:15Z ddc:004 open_access

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree Barak, Boaz Moitra, Ankur O’Donnell, Ryan Raghavendra, Prasad Regev, Oded Steurer, David Trevisan, Luca Vijayaraghavan, Aravindan Witmer, David Wright, John constraint satisfaction problems bounded degree advantage over random 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 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 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(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Boaz Barak and Ankur Moitra and Ryan O’Donnell and Prasad Raghavendra and Oded Regev and David Steurer and Luca Trevisan and Aravindan Vijayaraghavan and David Witmer and John Wright 2015 Is Part Of LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2015.110 urn:nbn:de:0030-drops-52981 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.110 eng https://creativecommons.org/licenses/by/3.0/legalcode