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...
| Main Authors: | , , , , , , , , , |
|---|---|
| Other Authors: | |
| 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 |
| _version_ | 1826206158773288960 |
|---|---|
| author | Barak, Boaz O'Donnell, Ryan Raghavendra, Prasad Regev, Oded Steurer, David Trevisan, Luca Vijayaraghavan, Aravindan Witmer, David Wright, John Moitra, Ankur |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Barak, Boaz O'Donnell, Ryan Raghavendra, Prasad Regev, Oded Steurer, David Trevisan, Luca Vijayaraghavan, Aravindan Witmer, David Wright, John Moitra, Ankur |
| author_sort | Barak, Boaz |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T13:25:01Z |
| format | Article |
| id | mit-1721.1/104772 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:25:01Z |
| publishDate | 2016 |
| publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik |
| record_format | dspace |
| spelling | mit-1721.1/1047722022-10-01T15:09:42Z Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree Barak, Boaz O'Donnell, Ryan Raghavendra, Prasad Regev, Oded Steurer, David Trevisan, Luca Vijayaraghavan, Aravindan Witmer, David Wright, John Moitra, Ankur Massachusetts Institute of Technology. Department of Mathematics Moitra, Ankur 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. 2016-10-06T22:02:37Z 2016-10-06T22:02:37Z 2015-08 Article http://purl.org/eprint/type/ConferencePaper 1868-8969 http://hdl.handle.net/1721.1/104772 Barak, Boaz et al. “Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree.” Leibniz International Proceedings in Informatics 40 (2015): n. pag. https://orcid.org/0000-0001-7047-0495 en_US http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.110 Leibniz International Proceedings in Informatics Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ application/pdf Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik Leibniz International Proceedings in Informatics |
| spellingShingle | Barak, Boaz O'Donnell, Ryan Raghavendra, Prasad Regev, Oded Steurer, David Trevisan, Luca Vijayaraghavan, Aravindan Witmer, David Wright, John Moitra, Ankur Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree |
| title | Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree |
| title_full | Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree |
| title_fullStr | Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree |
| title_full_unstemmed | Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree |
| title_short | Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree |
| title_sort | beating the random assignment on constraint satisfaction problems of bounded degree |
| url | http://hdl.handle.net/1721.1/104772 https://orcid.org/0000-0001-7047-0495 |
| work_keys_str_mv | AT barakboaz beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT odonnellryan beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT raghavendraprasad beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT regevoded beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT steurerdavid beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT trevisanluca beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT vijayaraghavanaravindan beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT witmerdavid beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT wrightjohn beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree AT moitraankur beatingtherandomassignmentonconstraintsatisfactionproblemsofboundeddegree |