Fetching the paper…

Reading the bibliography…

2021

Limitations of the Invertible-Map Equivalences

Dawar, Anuj, Grädel, Erich, Lichter, Moritz

Original
PDF
Post on X

Understand

This note draws conclusions that arise by combining two recent papers, by Anuj Dawar, Erich Gr\"adel, 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-F\"urer-Immerman (CFI) structures.
These $\equiv^\text{IM}_{k,Q}$-equivalences, for a number $k$ and a set of primes~$Q$, refine the well-known Weisfeiler-Leman 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$.

Limitations of the Invertible-Map Equivalences · Around

Built on

Regular graphs with given girth and restricted circuits
H. Sachs · 1963
Earlier work this paper cites.
An optimal lower bound on the number of variables for graph identification
J. Cai, M. Fürer, and N. Immerman · 1992
Earlier work this paper cites.
The quest for a logic capturing PTIME
M. Grohe · 2008
Earlier work this paper cites.
Affine systems of equations and counting infinitary logic
A. Atserias, A. Bulatov, and A. Dawar · 2009
Earlier work this paper cites.
Logics with rank operators
A. Dawar, M. Grohe, B. Holm, and B. Laubner · 2009
Earlier work this paper cites.

Similar

Descriptive Complexity of Linear Algebra
B. Holm · 2010
Cited alongside, same era.
A new bound for the connectivity of cages
C. Balbuena and J. Salas · 2012
Cited alongside, same era.
Definability of linear equation systems over groups and rings
A. Dawar, E. Grädel, B. Holm, E. Kopczynski, and W. Pakusa · 2013
Cited alongside, same era.
Pebble games with algebraic rules
A. Dawar and B. Holm · 2017
Cited alongside, same era.
Approximations of isomorphism and logics with linear-algebraic operators
Original
A. Dawar, E. Grädel, and W. Pakusa · 2019
Cited alongside, same era.

Then

Approximations of isomorphism and logics with linear-algebraic operators
A. Dawar, E. Grädel, and W. Pakusa · 2019
Later among the works it cites.
A finite-model-theoretic view on propositional proof complexity
E. Grädel, M. Grohe, B. Pago, and W. Pakusa · 2019
Later among the works it cites.
Rank logic is dead, long live rank logic!
E. Grädel and W. Pakusa · 2019
Later among the works it cites.
Separating rank logic from polynomial time
M. Lichter · 2021
Closest in time.
Separating rank logic from polynomial time
Original
M. Lichter · 2021
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…