Document Open Access Logo

Symmetries and Complexity (Invited Talk)

Author Andrei A. Bulatov

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.2.pdf
  • Filesize: 0.79 MB
  • 17 pages

Document Identifiers

Author Details

Andrei A. Bulatov
  • School of Computing Science, Simon Fraser University, Burnaby, Canada

Funding

  • Bulatov, Andrei A.: This research was supported by an NSERC Discovery grant.

Cite AsGet BibTex

Andrei A. Bulatov. Symmetries and Complexity (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 2:1-2:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.2

Abstract

The Constraint Satisfaction Problem (CSP) and a number of problems related to it have seen major advances during the past three decades. In many cases the leading driving force that made these advances possible has been the so-called algebraic approach that uses symmetries of constraint problems and tools from algebra to determine the complexity of problems and design solution algorithms. In this presentation we give a high level overview of the main ideas behind the algebraic approach illustrated by examples ranging from the regular CSP, to counting problems, to optimization and promise problems, to graph isomorphism.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Design and analysis of algorithms
Keywords
  • constraint problems
  • algebraic approach
  • dichotomy theorems

Metrics

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

References

  1. Albert Atserias and Joanna Ochremiak. Proof complexity meets algebra. ACM Trans. Comput. Log., 20(1):1:1-1:46, 2019. Google Scholar
  2. Miriam Backens and Leslie Ann Goldberg. Holant clones and the approximability of conservative holant problems. ACM Trans. Algorithms, 16(2):23:1-23:55, 2020. Google Scholar
  3. Libor Barto and Marcin Kozik. Robustly solvable constraint satisfaction problems. SIAM J. Comput., 45(4):1646-1669, 2016. Google Scholar
  4. Libor Barto, Andrei A. Krokhin, and Ross Willard. Polymorphisms, and how to use them. In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 1-44. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  5. Christoph Berkholz and Martin Grohe. Limitations of algebraic approaches to graph isomorphism testing. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 155-166. Springer, 2015. Google Scholar
  6. Manuel Bodirsky, Martin Hils, and Barnaby Martin. On the scope of the universal-algebraic approach to constraint satisfaction. Log. Methods Comput. Sci., 8(3), 2009. Google Scholar
  7. Manuel Bodirsky and Marcello Mamino. Constraint satisfaction problems over numeric domains. In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 79-111. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  8. V.G. Bodnarchuk, L.A. Kaluzhnin, V.N. Kotov, and B.A. Romov. Galois theory for Post algebras. I. Kibernetika, 3:1-10, 1969. Google Scholar
  9. Joshua Brakensiek and Venkatesan Guruswami. New hardness results for graph and hypergraph colorings. In Ran Raz, editor, 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, volume 50 of LIPIcs, pages 14:1-14:27. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  10. Joshua Brakensiek and Venkatesan Guruswami. Promise constraint satisfaction: Structure theory and a symmetric Boolean dichotomy. In Artur Czumaj, editor, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1782-1801. SIAM, 2018. Google Scholar
  11. Jonah Brown-Cohen and Prasad Raghavendra. Combinatorial optimization algorithms via polymorphisms. CoRR, abs/1501.01598, 2015. URL: http://arxiv.org/abs/1501.01598.
  12. Andrei Bulatov, Marcin Kozik, Peter Mayr, and Markus Steindl. The subpower membership problem for semigroups. Int. J. Algebra Comput., 26(7):1435-1451, 2016. Google Scholar
  13. Andrei A. Bulatov. The complexity of the Counting Constraint Satisfaction Problem. J. ACM, 60(5):34:1-34:41, 2013. Google Scholar
  14. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319-330, 2017. Google Scholar
  15. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs simplified. CoRR, abs/2007.09099, 2020. URL: http://arxiv.org/abs/2007.09099.
  16. Andrei A. Bulatov and Víctor Dalmau. A simple algorithm for Mal'tsev constraints. SIAM J. Comput., 36(1):16-27, 2006. Google Scholar
  17. Andrei A. Bulatov and Víctor Dalmau. Towards a dichotomy theorem for the Counting Constraint Satisfaction Problem. Inf. Comput., 205(5):651-678, 2007. Google Scholar
  18. Andrei A. Bulatov and Martin Grohe. The complexity of partition functions. Theor. Comput. Sci., 348(2-3):148-186, 2005. Google Scholar
  19. 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
  20. Andrei A. Bulatov and Dániel Marx. Constraint Satisfaction Problems and global cardinality constraints. Commun. ACM, 53(9):99-106, 2010. Google Scholar
  21. Andrei A. Bulatov and Dániel Marx. Constraint Satisfaction parameterized by solution size. SIAM J. Comput., 43(2):573-616, 2014. Google Scholar
  22. Andrei A. Bulatov and Akbar Rafiey. On the complexity of CSP-based ideal membership problems. CoRR, abs/2011.03700, 2020. URL: http://arxiv.org/abs/2011.03700.
  23. Jakub Bulín, Andrei A. Krokhin, and Jakub Oprsal. Algebraic approach to promise constraint satisfaction. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 602-613. ACM, 2019. Google Scholar
  24. Jin-Yi Cai and Xi Chen. Complexity dichotomies for counting problems. Volume 1: Boolean domain. Cambridge University Press, 2017. Google Scholar
  25. Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3):19:1-19:39, 2017. Google Scholar
  26. Hubie Chen, Matt Valeriote, and Yuichi Yoshida. Constant-query testability of assignments to Constraint Satisfaction Problems. SIAM J. Comput., 48(3):1022-1045, 2019. Google Scholar
  27. Hubie Chen and Matthew Valeriote. Learnability of solutions to conjunctive queries. J. Mach. Learn. Res., 20:67:1-67:28, 2019. Google Scholar
  28. Nadia Creignou, Sanjeev Khanna, and Madhu Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications. SIAM, 2001. Google Scholar
  29. Martin E. Dyer and Catherine S. Greenhill. The complexity of counting graph homomorphisms. Random Struct. Algorithms, 17(3-4):260-289, 2000. Google Scholar
  30. Martin E. Dyer and David Richerby. An effective dichotomy for the Counting Constraint Satisfaction Problem. SIAM J. Comput., 42(3):1245-1274, 2013. Google Scholar
  31. Tomas Feder and Moshe Y. Vardi. Monotone Monadic SNP and constraint satisfaction. In Proceedings of 25th ACM Symposium on the Theory of Computing (STOC), pages 612-622, 1993. Google Scholar
  32. Tomas Feder and Moshe Y. Vardi. The computational structure of Monotone Monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal of Computing, 28:57-104, 1998. Google Scholar
  33. Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, and Ivan Mihajlin. Lower bounds for the graph homomorphism problem. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, volume 9134 of Lecture Notes in Computer Science, pages 481-493. Springer, 2015. Google Scholar
  34. D. Geiger. Closed systems of function and predicates. Pacific Journal of Mathematics, pages 95-100, 1968. Google Scholar
  35. Martin Grohe and Pascal Schweitzer. The graph isomorphism problem. Commun. ACM, 63(11):128-134, 2020. Google Scholar
  36. J. Hagemann and A. Mitschke. On n-permutable congruences. Algebra Universalis, pages 8-12, 1973. Google Scholar
  37. D. Hobby and R.N. McKenzie. The Structure of Finite Algebras, volume 76 of Contemporary Mathematics. American Mathematical Society, Providence, R.I., 1988. Google Scholar
  38. Pawel M. Idziak, Petar Markovic, Ralph McKenzie, Matthew Valeriote, and Ross Willard. Tractability and learnability arising from algebras with few subpowers. SIAM J. Comput., 39(7):3023-3037, 2010. Google Scholar
  39. Peter Jeavons, David A. Cohen, and Marc Gyssens. Closure properties of constraints. J. ACM, 44(4):527-548, 1997. Google Scholar
  40. Peter G. Jeavons, David A. Cohen, and Martin C. Cooper. Constraints, consistency and closure. Artificial Intelligence, 101(1-2):251-265, 1998. Google Scholar
  41. Peter Jonsson, Victor Lagerkvist, and Biman Roy. Fine-grained time complexity of Constraint Satisfaction Problems. ACM Trans. Comput. Theory, 13(1):2:1-2:32, 2021. Google Scholar
  42. Ondrej Klíma, Pascal Tesson, and Denis Thérien. Dichotomies in the complexity of solving systems of equations over finite semigroups. Theory Comput. Syst., 40(3):263-297, 2007. Google Scholar
  43. Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-query containment and constraint satisfaction. In Alberto O. Mendelzon and Jan Paredaens, editors, Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, USA, pages 205-213. ACM Press, 1998. Google Scholar
  44. Richard Ladner. On the structure of polynomial time reducibility. Journal of the ACM, 22:155-171, 1975. Google Scholar
  45. Barnaby Martin. Quantified constraints in twenty seventeen. In Andrei A. Krokhin and Stanislav Zivný, editors, The Constraint Satisfaction Problem: Complexity and Approximability, volume 7 of Dagstuhl Follow-Ups, pages 327-346. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  46. Monaldo Mastrolilli. The complexity of the ideal membership problem for constrained problems over the Boolean domain. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 456-475. SIAM, 2019. Google Scholar
  47. Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1-17:24, 2008. Google Scholar
  48. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the 10th ACM Symposium on Theory of Computing (STOC'78), pages 216-226, 1978. Google Scholar
  49. Johan Thapper and Stanislav Zivný. The complexity of finite-valued CSPs. J. ACM, 63(4):37:1-37:33, 2016. Google Scholar
  50. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979. Google Scholar
  51. 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