{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T06:37:19Z","timestamp":1780382239989,"version":"3.54.1"},"reference-count":15,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T00:00:00Z","timestamp":1662422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100010663","name":"European Research Council","doi-asserted-by":"publisher","award":["820148"],"award-info":[{"award-number":["820148"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,7,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>This note draws conclusions that arise by combining two recent papers, by Anuj Dawar, Erich Gr\u00e4del and Wied Pakusa, published at ICALP 2019, and by Moritz Lichter, published at LICS 2021. In both papers, the main technical results rely on the combinatorial and algebraic analysis of the invertible-map equivalences ${\\equiv ^{\\text {IM}}_{k, Q}}$ on certain variants of Cai\u2013F\u00fcrer\u2013Immerman structures (CFI-structures for short). These ${\\equiv ^{\\text {IM}}_{k, Q}}$-equivalences, for a natural number $k$ and a set of primes $Q$, refine the well-known Weisfeiler\u2013Leman equivalences used in algorithms for graph isomorphism. The intuition is that two graphs $G{\\equiv ^{\\text {IM}}_{k, Q}}H$ cannot be distinguished by iterative refinements of equivalences on $k$-tuples defined via linear operators on vector spaces over fields of characteristic $p \\in Q$. In the first paper it has been shown, using considerable algebraic machinery, that for a prime $q \\notin Q$, the ${\\equiv ^{\\text {IM}}_{k, Q}}$ equivalences are not strong enough to distinguish between non-isomorphic CFI-structures over the field $\\mathbb {F}_q$. In the second paper, a similar but not identical construction for CFI-structures over the rings $\\mathbb {Z}_{2^i}$ has, again by rather involved combinatorial and algebraic arguments, been shown to be indistinguishable with respect to ${\\equiv ^{\\text {IM}}_{k, \\{2\\}}}$. Together with an earlier work on rank logic, this second result suffices to separate rank logic from polynomial time. We show here that the two approaches can be unified to prove that CFI-structures over the rings $\\mathbb {Z}_{2^i}$ are in fact indistinguishable with respect to ${\\equiv ^{\\text {IM}}_{k, {\\mathbb {P}}}}$, for the set ${\\mathbb {P}}$ of all primes. In particular, this implies the following two results. First, there is no fixed $k$ such that the invertible-map equivalence ${\\equiv ^{\\text {IM}}_{k, {\\mathbb {P}}}}$ coincides with isomorphism on all finite graphs. Second, no extension of fixed-point logic by linear-algebraic operators over fields can capture polynomial time.<\/jats:p>","DOI":"10.1093\/logcom\/exac058","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T08:21:23Z","timestamp":1662538883000},"page":"961-969","source":"Crossref","is-referenced-by-count":4,"title":["Limitations of the invertible-map equivalences"],"prefix":"10.1093","volume":"33","author":[{"given":"Anuj","family":"Dawar","sequence":"first","affiliation":[{"name":"Department of Computer Science and Technology , University of Cambridge, Cambridge CB3 0FD, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erich","family":"Gr\u00e4del","sequence":"additional","affiliation":[{"name":"Mathematical Foundations of Computer Science , RWTH Aachen University, D-52056 Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moritz","family":"Lichter","sequence":"additional","affiliation":[{"name":"Fachbereich Mathematik , TU Darmstadt, D-64289 Darmstadt, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2022,9,6]]},"reference":[{"key":"2023072417264306400_ref1","doi-asserted-by":"crossref","first-page":"1666","DOI":"10.1016\/j.tcs.2008.12.049","article-title":"Affine systems of equations and counting infinitary logic","volume":"410","author":"Atserias","year":"2009","journal-title":"Theoretical Computer Science"},{"key":"2023072417264306400_ref2","doi-asserted-by":"crossref","first-page":"1676","DOI":"10.1016\/j.aml.2012.01.036","article-title":"A new bound for the connectivity of cages","volume":"25","author":"Balbuena","year":"2012","journal-title":"Applied Mathematics Letters"},{"key":"2023072417264306400_ref3","doi-asserted-by":"crossref","first-page":"389","DOI":"10.1007\/BF01305232","article-title":"An optimal lower bound on the number of variables for graph identification","volume":"12","author":"Cai","year":"1992","journal-title":"Combinatorica"},{"key":"2023072417264306400_ref4","article-title":"Definability of linear equation systems over groups and rings","volume":"9","author":"Dawar","year":"2013","journal-title":"Logical Methods in Computer Science"},{"key":"2023072417264306400_ref5","article-title":"Approximations of isomorphism and logics with linear-algebraic operators","author":"Dawar","year":"2019","journal-title":"CoRR"},{"key":"2023072417264306400_ref6","first-page":"112:1","article-title":"Approximations of isomorphism and logics with linear-algebraic operators","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","author":"Dawar","year":"2019"},{"key":"2023072417264306400_ref7","first-page":"113","article-title":"Logics with rank operators","volume-title":"Proceedings of LICS 2009","author":"Dawar","year":"2009"},{"key":"2023072417264306400_ref8","doi-asserted-by":"crossref","first-page":"281","DOI":"10.3233\/FI-2017-1471","article-title":"Pebble games with algebraic rules","volume":"150","author":"Dawar","year":"2017","journal-title":"Fundamenta Informaticae"},{"key":"2023072417264306400_ref9","first-page":"4:1","article-title":"A finite-model-theoretic view on propositional proof complexity","volume":"15:1","author":"Gr\u00e4del","year":"2019","journal-title":"Logical Methods in Computer Science"},{"key":"2023072417264306400_ref10","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1017\/jsl.2018.33","article-title":"Rank logic is dead, long live rank logic!","volume":"84","author":"Gr\u00e4del","year":"2019","journal-title":"Journal of Symbolic Logic"},{"key":"2023072417264306400_ref11","first-page":"267","article-title":"The quest for a logic capturing PTIME","volume-title":"Proceedings of the 23rd IEEE Symposium on Logic in Computer Science, LICS 2008","author":"Grohe","year":"2008"},{"key":"2023072417264306400_ref12","volume-title":"Descriptive Complexity of Linear Algebra","author":"Holm","year":"2010"},{"key":"2023072417264306400_ref13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/LICS52264.2021.9470598","article-title":"Separating rank logic from polynomial time","volume-title":"36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021","author":"Lichter","year":"2021"},{"key":"2023072417264306400_ref14","article-title":"Separating rank logic from polynomial time","author":"Lichter","year":"2021","journal-title":"CoRR"},{"key":"2023072417264306400_ref15","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1112\/jlms\/s1-38.1.423","article-title":"Regular graphs with given girth and restricted circuits","volume":"s1\u201338","author":"Sachs","year":"1963","journal-title":"Journal of the London Mathematical Society. Second Series"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/5\/961\/50948091\/exac058.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/5\/961\/50948091\/exac058.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T17:26:56Z","timestamp":1690219616000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/33\/5\/961\/6687793"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,6]]},"references-count":15,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,9,6]]},"published-print":{"date-parts":[[2023,7,25]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exac058","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,7]]},"published":{"date-parts":[[2022,9,6]]}}}