Show simple item record

dc.contributor.authorDawar, Anujen
dc.contributor.authorGrädel, Een
dc.contributor.authorPakusa, Wen
dc.date.accessioned2020-01-07T00:30:42Z
dc.date.available2020-01-07T00:30:42Z
dc.date.issued2019-07-01en
dc.identifier.isbn9783959771092en
dc.identifier.issn1868-8969
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/300516
dc.description.abstractInvertible 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.
dc.publisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
dc.rightsAttribution 4.0 International
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.titleApproximations of isomorphism and logics with linear-algebraic operatorsen
dc.typeConference Object
prism.publicationDate2019en
prism.publicationNameLeibniz International Proceedings in Informatics, LIPIcsen
prism.volume132en
dc.identifier.doi10.17863/CAM.47590
dcterms.dateAccepted2019-06-01en
rioxxterms.versionofrecord10.4230/LIPIcs.ICALP.2019.112en
rioxxterms.versionVoR
rioxxterms.licenseref.urihttp://creativecommons.org/licenses/by/4.0/en
rioxxterms.licenseref.startdate2019-07-01en
dc.contributor.orcidDawar, Anuj [0000-0003-4014-8248]
rioxxterms.typeConference Paper/Proceeding/Abstracten
pubs.funder-project-idEPSRC (EP/S03238X/1)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution 4.0 International
Except where otherwise noted, this item's licence is described as Attribution 4.0 International