Document Open Access Logo

Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

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

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2015.110.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

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

Cite As Get BibTex

Boaz Barak, Ankur Moitra, Ryan O’Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, and John Wright. Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 110-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.110

Abstract

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.

Subject Classification

Keywords
  • constraint satisfaction problems
  • bounded degree
  • advantage over random

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Noga Alon. On the edge-expansion of graphs. Combin. Probab. Comput., 6(2):145-152, 1997. Google Scholar
  2. Bonnie Berger and Peter W. Shor. Approximation alogorithms for the maximum acyclic subgraph problem. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'90, pages 236-243, Philadelphia, PA, USA, 1990. Society for Industrial and Applied Mathematics. Google Scholar
  3. Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O'Donnell. On the Fourier tails of bounded functions over the discrete cube. Israel J. Math., 160:389-412, 2007. Google Scholar
  4. Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm applied to a bounded occurrence constraint problem, 2014. arXiv:1412.6062. Google Scholar
  5. Venkatesan Guruswami and Yuan Zhou. Approximating bounded occurrence ordering csps. In Anupam Gupta, Klaus Jansen, José Rolim, and Rocco Servedio, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, volume 7408 of Lecture Notes in Computer Science, pages 158-169. Springer Berlin Heidelberg, 2012. Google Scholar
  6. Johan Håstad. On bounded occurrence constraint satisfaction. Inform. Process. Lett., 74(1-2):1-6, 2000. Google Scholar
  7. Johan Håstad. Some optimal inapproximability results. J. ACM, 48(4):798-859, 2001. Google Scholar
  8. Johan Håstad and S. Venkatesh. On the advantage over a random assignment. Random Structures Algorithms, 25(2):117-149, 2004. Google Scholar
  9. Subhash Khot and Assaf Naor. Linear equations modulo 2 and the L \sb 1 diameter of convex bodies. SIAM J. Comput., 38(4):1448-1463, 2008. Google Scholar
  10. Konstantin Makarychev. Local search is better than random assignment for bounded occurrence ordering k-csps. In 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany, pages 139-147, 2013. Google Scholar
  11. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  12. James B. Shearer. A note on bipartite subgraphs of triangle-free graphs. Random Structures Algorithms, 3(2):223-226, 1992. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact