文章基本信息

标题：Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree
本地全文：下载
作者：Boaz Barak ; Ankur Moitra ; Ryan O'Donnell 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：40
页码：110-123
DOI：10.4230/LIPIcs.APPROX-RANDOM.2015.110
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：constraint satisfaction problems; bounded degree; advantage over random