Document Open Access Logo

Cohomology in Constraint Satisfaction and Structure Isomorphism

Author Adam Ó Conghaile

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.75.pdf
  • Filesize: 0.78 MB
  • 16 pages

Document Identifiers

Author Details

Adam Ó Conghaile
  • Computer Laboratory, Cambridge University, United Kingdom
  • The Alan Turing Institute, United Kingdom

Funding

Funded in part by EPSRC grants EP/R513180/1 and EP/S03238X/1 and supported by a PhD Enrichment Award from the Alan Turing Institute.

Acknowledgements

I thank Anuj Dawar and Samson Abramsky for useful discussions in writing this paper and am especially gratefully to Samson Abramsky for permission to use results from [Abramsky, 2022].

Cite AsGet BibTex

Adam Ó Conghaile. Cohomology in Constraint Satisfaction and Structure Isomorphism. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 75:1-75:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.MFCS.2022.75

Abstract

Constraint satisfaction (CSP) and structure isomorphism (SI) are among the most well-studied computational problems in Computer Science. While neither problem is thought to be in PTIME, much work is done on PTIME approximations to both problems. Two such historically important approximations are the k-consistency algorithm for CSP and the k-Weisfeiler-Leman algorithm for SI, both of which are based on propagating local partial solutions. The limitations of these algorithms are well-known – k-consistency can solve precisely those CSPs of bounded width and k-Weisfeiler-Leman can only distinguish structures which differ on properties definable in C^k. In this paper, we introduce a novel sheaf-theoretic approach to CSP and SI and their approximations. We show that both problems can be viewed as deciding the existence of global sections of presheaves, ℋ_k(A,B) and ℐ_k(A,B) and that the success of the k-consistency and k-Weisfeiler-Leman algorithms correspond to the existence of certain efficiently computable subpresheaves of these. Furthermore, building on work of Abramsky and others in quantum foundations, we show how to use Čech cohomology in ℋ_k(A,B) and ℐ_k(A,B) to detect obstructions to the existence of the desired global sections and derive new efficient cohomological algorithms extending k-consistency and k-Weisfeiler-Leman. We show that cohomological k-consistency can solve systems of equations over all finite rings and that cohomological Weisfeiler-Leman can distinguish positive and negative instances of the Cai-Fürer-Immerman property over several important classes of structures.

Subject Classification

ACM Subject Classification
  • Theory of computation → Finite Model Theory
Keywords
  • constraint satisfaction problems
  • finite model theory
  • descriptive complexity
  • rank logic
  • Weisfeiler-Leman algorithm
  • cohomology

Metrics

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

Related Versions

References

  1. Samson Abramsky. Notes on presheaf representations of strategies and cohomological refinements of k-consistency and k-equivalence, 2022. URL: https://doi.org/10.48550/ARXIV.2206.12156.
  2. Samson Abramsky, Rui Soares Barbosa, Kohei Kishida, Raymond Lal, and Shane Mansfield. Contextuality, Cohomology and Paradox. In Stephan Kreutzer, editor, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015), volume 41 of Leibniz International Proceedings in Informatics (LIPIcs), pages 211-228, Dagstuhl, Germany, 2015. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CSL.2015.211.
  3. Samson Abramsky and Adam Brandenburger. The sheaf-theoretic structure of non-locality and contextuality. New Journal of Physics, 13(11):113036, November 2011. URL: https://doi.org/10.1088/1367-2630/13/11/113036.
  4. Samson Abramsky, Anuj Dawar, and Pengming Wang. The pebbling comonad in finite model theory. In Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '17. IEEE Press, 2017. Google Scholar
  5. Samson Abramsky, Shane Mansfield, and Rui Soares Barbosa. The cohomology of non-locality and contextuality. In B. Jacobs, P. Selinger, and B. Spitters, editors, Proceedings of 8th International Workshop on Quantum Physics and Logic (QPL 2011), volume 95, pages 1-14, 2011. URL: https://doi.org/10.4204/EPTCS.95.1.
  6. Albert Atserias, Andrei Bulatov, and Anuj Dawar. Affine systems of equations and counting infinitary logic. In In ICALP’07, volume 4596 of LNCS, pages 558-570, 2007. Google Scholar
  7. Albert Atserias, Andrei A. Bulatov, and Víctor Dalmau. On the power of k -consistency. In Lars Arge, Christian Cachin, Tomasz Jurdzinski, and Andrzej Tarlecki, editors, Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings, volume 4596 of Lecture Notes in Computer Science, pages 279-290. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-73420-8_26.
  8. László Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, STOC '16, pages 684-697, New York, NY, USA, 2016. Association for Computing Machinery. URL: https://doi.org/10.1145/2897518.2897542.
  9. Christoph Berkholz and Martin Grohe. Linear diophantine equations, group CSPs, and graph isomorphism. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 327-339. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.21.
  10. Mikolaj Bojanczyk, Bartek Klin, Slawomir Lasota, and Szymon Torunczyk. Turing machines with atoms. In 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 183-192, 2013. URL: https://doi.org/10.1109/LICS.2013.24.
  11. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, and Stanislav Živný. The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems. SIAM Journal on Computing, 49(6):1232-1248, 2020. URL: https://doi.org/10.1137/20M1312745.
  12. Andrei A. Bulatov. A dichotomy theorem for nonuniform CSPs. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 319-330, 2017. URL: https://doi.org/10.1109/FOCS.2017.37.
  13. Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):389-410, December 1992. URL: https://doi.org/10.1007/BF01305232.
  14. Lorenzo Ciardo and Stanislav Zivný. CLAP: A new algorithm for promise CSPs. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1057-1068. SIAM, 2022. URL: https://doi.org/10.1137/1.9781611977073.46.
  15. Anuj Dawar, Erich Grädel, and Wied Pakusa. Approximations of Isomorphism and Logics with Linear-Algebraic Operators. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), pages 112:1-112:14, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.112.
  16. Anuj Dawar, Erich Grädel, and Moritz Lichter. Limitations of the invertible-map equivalences, 2021. URL: http://arxiv.org/abs/2109.07218.
  17. Anuj Dawar and Bjarki Holm. Pebble games with algebraic rules. In Artur Czumaj, Kurt Mehlhorn, Andrew Pitts, and Roger Wattenhofer, editors, Automata, Languages, and Programming, pages 251-262, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  18. 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 Journal on Computing, 28(1):57-104, 1998. URL: https://doi.org/10.1137/S0097539794266766.
  19. Marcelo Fiore and Sam Staton. Comparing operational models of name-passing process calculi. Information and Computation, 204(4):524-560, 2006. Seventh Workshop on Coalgebraic Methods in Computer Science 2004. URL: https://doi.org/10.1016/j.ic.2005.08.004.
  20. Jörg Flum and Martin Grohe. On fixed-point logic with counting. The Journal of Symbolic Logic, 65(2):777-787, 2000. URL: http://www.jstor.org/stable/2586569.
  21. Roger Godement. Topologie algébrique et théorie des faisceaux. The Mathematical Gazette, 44:69, 1960. Google Scholar
  22. Alexander Grothendieck. Sur quelques points d'algèbre homologique, I. Tohoku Mathematical Journal, 9(2):119-221, 1957. URL: https://doi.org/10.2748/tmj/1178244839.
  23. Yuri Gurevich. Logic and the challenge of computer science, 1988. Google Scholar
  24. Lauri Hella. Logical hierarchies in PTIME. Information and Computation, 129(1):1-19, 1996. URL: https://doi.org/10.1006/inco.1996.0070.
  25. Neil Immerman and Eric Lander. Describing Graphs: A First-Order Approach to Graph Canonization, pages 59-81. Springer New York, New York, NY, 1990. URL: https://doi.org/10.1007/978-1-4612-4478-3_5.
  26. Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the smith and hermite normal forms of an integer matrix. SIAM Journal on Computing, 8(4):499-9, November 1979. Copyright - Copyright] © 1979 © Society for Industrial and Applied Mathematics; Last updated - 2021-09-11. URL: https://ezp.lib.cam.ac.uk/login?url=https://www.proquest.com/scholarly-journals/polynomial-algorithms-computing-smith-hermite/docview/918468506/se-2?accountid=9851.
  27. Sandra Kiefer. Power and limits of the Weisfeiler-Leman algorithm. Dissertation, RWTH Aachen University, Aachen, 2020. Veröffentlicht auf dem Publikationsserver der RWTH Aachen University; Dissertation, RWTH Aachen University, 2020. URL: https://doi.org/10.18154/RWTH-2020-03508.
  28. P.G. Kolaitis and M.Y. Vardi. On the expressive power of Datalog: Tools and a case study. Journal of Computer and System Sciences, 51(1):110-134, 1995. URL: https://doi.org/10.1006/jcss.1995.1055.
  29. Tom Leinster. Categories, functors and natural transformations, pages 9-40. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2014. URL: https://doi.org/10.1017/CBO9781107360068.003.
  30. Moritz Lichter. Separating rank logic from polynomial time. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-13. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470598.
  31. Saunders Mac Lane and Ieke Moerdijk. Sheaves of Sets, pages 64-105. Springer New York, New York, NY, 1994. URL: https://doi.org/10.1007/978-1-4612-0927-0_4.
  32. Cristina Matache, Sean K. Moss, and Sam Staton. Recursion and sequentiality in categories of sheaves. In Naoki Kobayashi, editor, 6th International Conference on Formal Structures for Computation and Deduction, FSCD 2021, July 17-24, 2021, Buenos Aires, Argentina (Virtual Conference), volume 195 of LIPIcs, pages 25:1-25:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.FSCD.2021.25.
  33. Baudot P. and Bennequin D. The homological nature of entropy. Entropy, 17(5):3253-3318, 2015. Cited by: 27; All Open Access, Gold Open Access, Green Open Access. URL: https://doi.org/10.3390/e17053253.
  34. Wied Pakusa. Linear Equation Systems and the Search for a Logical Characterisation of Polynomial Time. PhD thesis, RWTH Aachen University, 2016. URL: https://logic.rwth-aachen.de/~pakusa/diss.pdf.
  35. Dmitriy Zhuk. A proof of the CSP dichotomy conjecture. J. ACM, 67(5), August 2020. URL: https://doi.org/10.1145/3402029.
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