Document Open Access Logo

Conditional Dichotomy of Boolean Ordered Promise CSPs

Authors Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.37.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Author Details

Joshua Brakensiek
  • Computer Science Department, Stanford University, CA, USA
Venkatesan Guruswami
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA
Sai Sandeep
  • Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Brakensiek, Joshua: Research supported in part by an NSF Graduate Research Fellowship.
  • Guruswami, Venkatesan: Research supported in part by NSF grant CCF-1908125 and a Simons Investigator award.
  • Sandeep, Sai: Research supported in part by NSF grants CCF-1563742 and CCF-1908125.

Acknowledgements

We thank Libor Barto, whose talk [Libor Barto, 2018] and insightful discussions inspired our work.

Cite AsGet BibTex

Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. Conditional Dichotomy of Boolean Ordered Promise CSPs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.37

Abstract

Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their formal introduction by Austrin, Guruswami, and Håstad [Per Austrin et al., 2017], there has been a flurry of works on PCSPs, including recent breakthroughs in approximate graph coloring [Barto et al., 2018; Andrei A. Krokhin and Jakub Opršal, 2019; Marcin Wrochna and Stanislav Zivný, 2020]. The key tool in studying PCSPs is the algebraic framework developed in the context of CSPs where the closure properties of the satisfying solutions known as polymorphisms are analyzed. The polymorphisms of PCSPs are significantly richer than CSPs - even in the Boolean case, we still do not know if there exists a dichotomy result for PCSPs analogous to Schaefer’s dichotomy result [Thomas J. Schaefer, 1978] for CSPs. In this paper, we study a special case of Boolean PCSPs, namely Boolean Ordered PCSPs where the Boolean PCSPs have the predicate x ≤ y. In the algebraic framework, this is the special case of Boolean PCSPs when the polymorphisms are monotone functions. We prove that Boolean Ordered PCSPs exhibit a computational dichotomy assuming the Rich 2-to-1 Conjecture [Mark Braverman et al., 2021] which is a perfect completeness surrogate of the Unique Games Conjecture. In particular, assuming the Rich 2-to-1 Conjecture, we prove that a Boolean Ordered PCSP can be solved in polynomial time if for every ε > 0, it has polymorphisms where each coordinate has Shapley value at most ε, else it is NP-hard. The algorithmic part of our dichotomy result is based on a structural lemma showing that Boolean monotone functions with each coordinate having low Shapley value have arbitrarily large threshold functions as minors. The hardness part proceeds by showing that the Shapley value is consistent under a uniformly random 2-to-1 minor. As a structural result of independent interest, we construct an example to show that the Shapley value can be inconsistent under an adversarial 2-to-1 minor.

Subject Classification

ACM Subject Classification
  • Theory of computation → Constraint and logic programming
  • Theory of computation → Approximation algorithms analysis
  • Theory of computation → Problems, reductions and completeness
  • Applied computing → Economics
Keywords
  • promise constraint satisfaction
  • Boolean ordered PCSP
  • Shapley value
  • rich 2-to-1 conjecture
  • random minor

Metrics

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

Related Versions

References

  1. Per Austrin, Venkatesan Guruswami, and Johan Håstad. (2+ε)-SAT is NP-hard. SIAM J. Comput., 46(5):1554-1573, 2017. Google Scholar
  2. Libor Barto. Cyclic operations in promise constraint satisfaction problems. Dagstuhl workshop The Constraint Satisfaction Problem: Complexity and Approximability, Schloss Dagstuhl, Germany, 2018. Available at URL: https://www2.karlin.mff.cuni.cz/~barto/Articles/Barto_Dagstuhl18.pdf.
  3. Libor Barto. Personal communication, 2018-20. Google Scholar
  4. Libor Barto, Jakub Bulín, Andrei Krokhin, and Jakub Opršal. Algebraic approach to promise constraint satisfaction. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.00970.
  5. Joshua Brakensiek and Venkatesan Guruswami. New hardness results for graph and hypergraph colorings. In 31st Conference on Computational Complexity, CCC 2016, pages 14:1-14:27, 2016. Google Scholar
  6. Joshua Brakensiek and Venkatesan Guruswami. Promise constraint satisfaction: Structure theory and a symmetric Boolean dichotomy. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 1782-1801, 2018. Google Scholar
  7. Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. Conditional dichotomy of boolean ordered promise csps. arXiv preprint, 2021. URL: http://arxiv.org/abs/2102.11854.
  8. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Zivný. The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems. SIAM J. Comput., 49(6):1232-1248, 2020. Google Scholar
  9. Mark Braverman, Subhash Khot, and Dor Minzer. On rich 2-to-1 games. In 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, volume 185 of LIPIcs, pages 27:1-27:20, 2021. Google Scholar
  10. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, pages 319-330. IEEE Computer Society, 2017. Google Scholar
  11. Andrei A. Bulatov, Peter Jeavons, and Andrei A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM J. Comput., 34(3):720-742, 2005. Google Scholar
  12. Anindya De, Ilias Diakonikolas, and Rocco A. Servedio. The inverse Shapley value problem. Games Econ. Behav., 105:122-147, 2017. Google Scholar
  13. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. On non-optimally expanding sets in grassmann graphs. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018,, pages 940-951. ACM, 2018. Google Scholar
  14. Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra. Towards a proof of the 2-to-1 games conjecture? In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018,, pages 376-389. ACM, 2018. Google Scholar
  15. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, 1998. Google Scholar
  16. Miron Ficak, Marcin Kozik, Miroslav Olsák, and Szymon Stankiewicz. Dichotomy for symmetric boolean PCSPs. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, volume 132 of LIPIcs, pages 57:1-57:12, 2019. Google Scholar
  17. Peter Jeavons. On the algebraic structure of combinatorial problems. Theor. Comput. Sci., 200(1-2):185-204, 1998. Google Scholar
  18. Peter Jeavons, David A. Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, 1997. Google Scholar
  19. Gil Kalai. Social indeterminacy. Econometrica, 72(5):1565-1581, 2004. Google Scholar
  20. Subhash Khot. Hardness results for coloring 3-colorable 3-uniform hypergraphs. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2002, pages 23-32. IEEE, 2002. Google Scholar
  21. Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings on 34th Annual ACM Symposium on Theory of Computing, STOC 2002, pages 767-775. ACM, 2002. Google Scholar
  22. Subhash Khot, Dor Minzer, and Muli Safra. On independent sets, 2-to-2 games, and grassmann graphs. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017,, pages 576-589. ACM, 2017. Google Scholar
  23. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in Grassmann graph have near-perfect expansion. In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, pages 592-601. IEEE Computer Society, 2018. Google Scholar
  24. Andrei A. Krokhin and Jakub Opršal. The complexity of 3-colouring H-colourable graphs. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, pages 1227-1239. IEEE Computer Society, 2019. Google Scholar
  25. G. A. Margulis. Probabilistic characteristics of graphs with large connectivity (in Russian). Probl. Pered. Inform., 10:101-108, 1974. Google Scholar
  26. Tomasz P. Michalak, Aadithya V. Karthik, Piotr L. Szczepanski, Balaraman Ravindran, and Nicholas R. Jennings. Efficient computation of the Shapley value for game-theoretic network centrality. J. Artif. Intell. Res., 46:607-650, 2013. Google Scholar
  27. Ramasuri Narayanam and Yadati Narahari. A Shapley value-based approach to discover influential nodes in social networks. IEEE Trans Autom. Sci. Eng., 8(1):130-147, 2011. Google Scholar
  28. Ryan O'Donnell. Analysis of Boolean Functions. Cambridge University Press, 2014. Google Scholar
  29. Jan Petr. Monotone functions avoiding majorities, 2020. Undergraduate Thesis. Univerzita Karlova, Matematicko-fyzikální fakulta. Google Scholar
  30. Nicholas Pippenger. Galois theory for minors of finite functions. Discrete Mathematics, 254(1-3):405-419, 2002. Google Scholar
  31. Lucio Russo. An approximate zero-one law. Z. Wahrscheinlichkeitstheorie und Verwandte Gebiete, 61(1):129-139, 1982. Google Scholar
  32. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, STOC 1978, pages 216-226. ACM, 1978. Google Scholar
  33. L. S. Shapley and Martin Shubik. A method for evaluating the distribution of power in a committee system. American Political Science Review, 48(3):787–792, 1954. Google Scholar
  34. Robert Weber. Probabilistic values for games. Cowles Foundation Discussion Papers 471R, Cowles Foundation for Research in Economics, Yale University, 1977. URL: https://EconPapers.repec.org/RePEc:cwl:cwldpp:471r.
  35. Marcin Wrochna and Stanislav Zivný. Improved hardness for H-colourings of G-colourable graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, pages 1426-1435. SIAM, 2020. Google Scholar
  36. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5):30:1-30:78, 2020. 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 Imprint Privacy Contact