2026-07-23T00:29:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14477 2024-03-06T10:54:07Z ddc:004 open_access

On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism Dawar, Anuj Vagnozzi, Danny Graph isomorphism proof complexity invertible map tests We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the invertible map tests (introduced by Dawar and Holm) and proof systems with algebraic rules, namely polynomial calculus, monomial calculus and Nullstellensatz calculus. In the case of fields of characteristic zero, these variants are all essentially equivalent to the Weisfeiler-Leman algorithms. In positive characteristic we show that the distinguishing power of the monomial calculus is no greater than the invertible map method by simulating the former in a fixed-point logic with solvability operators. In turn, we show that the distinctions made by this logic can be implemented in the Nullstellensatz calculus. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anuj Dawar and Danny Vagnozzi 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.37 urn:nbn:de:0030-drops-144774 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.37 eng https://creativecommons.org/licenses/by/4.0/legalcode