Dawar, Anuj ;
Grädel, Erich ;
Pakusa, Wied
Approximations of Isomorphism and Logics with LinearAlgebraic Operators
Abstract
Invertible map equivalences are approximations of graph isomorphism that refine the wellknown WeisfeilerLeman method. They are parameterized by a number k and a set Q of primes. The intuition is that two equivalent graphs G equiv^IM_{k, Q} H cannot be distinguished by means of partitioning the set of ktuples in both graphs with respect to any linearalgebraic operator acting on vector spaces over fields of characteristic p, for any p in Q. These equivalences have first appeared in the study of rank logic, but in fact they can be used to delimit the expressive power of any extension of fixedpoint logic with linearalgebraic operators. We define {LA^{k}}(Q), an infinitary logic with k variables and all linearalgebraic operators over finite vector spaces of characteristic p in Q and show that equiv^IM_{k, Q} is the natural notion of elementary equivalence for this logic. The logic LA^{omega}(Q) = Cup_{k in omega} LA^{k}(Q) is then a natural upper bound on the expressive power of any extension of fixedpoint logics by means of Qlinearalgebraic operators.
By means of a new and much deeper algebraic analysis of a generalized variant, for any prime p, of the CFIstructures due to Cai, Fürer, and Immerman, we prove that, as long as Q is not the set of all primes, there is no k such that equiv^IM_{k, Q} is the same as isomorphism. It follows that there are polynomialtime properties of graphs which are not definable in LA^{omega}(Q), which implies that no extension of fixedpoint logic with linearalgebraic operators can capture PTIME, unless it includes such operators for all prime characteristics. Our analysis requires substantial algebraic machinery, including a homogeneity property of CFIstructures and Maschke's Theorem, an important result from the representation theory of finite groups.
BibTeX  Entry
@InProceedings{dawar_et_al:LIPIcs:2019:10688,
author = {Anuj Dawar and Erich Gr{\"a}del and Wied Pakusa},
title = {{Approximations of Isomorphism and Logics with LinearAlgebraic Operators}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {112:1112:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10688},
URN = {urn:nbn:de:0030drops106887},
doi = {10.4230/LIPIcs.ICALP.2019.112},
annote = {Keywords: Finite Model Theory, Graph Isomorphism, Descriptive Complexity, Algebra}
}
2019
Keywords: 

Finite Model Theory, Graph Isomorphism, Descriptive Complexity, Algebra 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

2019 