## Approximations of isomorphism and logics with linear-algebraic operators

##### View / Open Files

##### Publication Date

2019-07-01##### Journal Title

Leibniz International Proceedings in Informatics, LIPIcs

##### ISSN

1868-8969

##### ISBN

9783959771092

##### Publisher

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

##### Volume

132

##### Type

Conference Object

##### This Version

VoR

##### Metadata

Show full item record##### Citation

Dawar, A., Grädel, E., & Pakusa, W. (2019). Approximations of isomorphism and logics with linear-algebraic operators. Leibniz International Proceedings in Informatics, LIPIcs, 132 https://doi.org/10.4230/LIPIcs.ICALP.2019.112

##### Abstract

Invertible map equivalences are approximations of graph isomorphism that refine the well-known Weisfeiler-Leman method. They are parameterized by a number k and a set Q of primes. The intuition is that two equivalent graphs G ≡IMk,Q H cannot be distinguished by means of partitioning the set of k-tuples in both graphs with respect to any linear-algebraic operator acting on vector spaces over fields of characteristic p, for any p ∈ 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 fixed-point logic with linear-algebraic operators. We define LAk(Q), an infinitary logic with k variables and all linear-algebraic operators over finite vector spaces of characteristic p ∈ Q and show that ≡IMk,Q is the natural notion of elementary equivalence for this logic. The logic LAω(Q) = Sk∈ω LAk(Q) is then a natural upper bound on the expressive power of any extension of fixed-point logics by means of Q-linear-algebraic operators. By means of a new and much deeper algebraic analysis of a generalized variant, for any prime p, of the CFI-structures 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 ≡IMk,Q is the same as isomorphism. It follows that there are polynomial-time properties of graphs which are not definable in LAω(Q), which implies that no extension of fixed-point logic with linear-algebraic operators can capture PTIME, unless it includes such operators for all prime characteristics. Our analysis requires substantial algebraic machinery, including a homogeneity property of CFI-structures and Maschke's Theorem, an important result from the representation theory of finite groups.

##### Sponsorship

EPSRC (EP/S03238X/1)

##### Identifiers

External DOI: https://doi.org/10.4230/LIPIcs.ICALP.2019.112

This record's URL: https://www.repository.cam.ac.uk/handle/1810/300516