Approximations of isomorphism and logics with linearalgebraic operators
dc.contributor.author  Dawar, Anuj  en 
dc.contributor.author  Grädel, E  en 
dc.contributor.author  Pakusa, W  en 
dc.date.accessioned  20200107T00:30:42Z  
dc.date.available  20200107T00:30:42Z  
dc.date.issued  20190701  en 
dc.identifier.isbn  9783959771092  en 
dc.identifier.issn  18688969  
dc.identifier.uri  https://www.repository.cam.ac.uk/handle/1810/300516  
dc.description.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 ≡IMk,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 ∈ 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 LAk(Q), an infinitary logic with k variables and all linearalgebraic 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 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 ≡IMk,Q is the same as isomorphism. It follows that there are polynomialtime properties of graphs which are not definable in LAω(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.  
dc.publisher  Schloss DagstuhlLeibnizZentrum fuer Informatik  
dc.rights  Attribution 4.0 International  
dc.rights.uri  https://creativecommons.org/licenses/by/4.0/  
dc.title  Approximations of isomorphism and logics with linearalgebraic operators  en 
dc.type  Conference Object  
prism.publicationDate  2019  en 
prism.publicationName  Leibniz International Proceedings in Informatics, LIPIcs  en 
prism.volume  132  en 
dc.identifier.doi  10.17863/CAM.47590  
dcterms.dateAccepted  20190601  en 
rioxxterms.versionofrecord  10.4230/LIPIcs.ICALP.2019.112  en 
rioxxterms.version  VoR  
rioxxterms.licenseref.uri  http://creativecommons.org/licenses/by/4.0/  en 
rioxxterms.licenseref.startdate  20190701  en 
dc.contributor.orcid  Dawar, Anuj [0000000340148248]  
rioxxterms.type  Conference Paper/Proceeding/Abstract  en 
pubs.funderprojectid  EPSRC (EP/S03238X/1) 
Files in this item
This item appears in the following Collection(s)

Cambridge University Research Outputs
Research outputs of the University of Cambridge