License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.37
URN: urn:nbn:de:0030-drops-144774
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14477/
Go to the corresponding LIPIcs Volume Portal

Dawar, Anuj ; Vagnozzi, Danny

On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism

pdf-format:
LIPIcs-MFCS-2021-37.pdf (0.8 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{dawar_et_al:LIPIcs.MFCS.2021.37,
  author =	{Dawar, Anuj and Vagnozzi, Danny},
  title =	{{On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14477},
  URN =		{urn:nbn:de:0030-drops-144774},
  doi =		{10.4230/LIPIcs.MFCS.2021.37},
  annote =	{Keywords: Graph isomorphism, proof complexity, invertible map tests}
}

Keywords: Graph isomorphism, proof complexity, invertible map tests
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI