3 papers
cs.LO2026
Subgroup Accessibility in Group Order Logic
Anatole Dahan
We investigate the expressive power of fixed-point logics (FP) and their extensions in defining generating sets for accessible subgroups of definable permutation groups. This opera…
cs.DS2026
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Anatole Dahan, Martin Grohe, Daniel Neuen +1
We present an additive -approximation algorithm for the Graph Edit Distance problem (GED) on graphs of VC dimension running in time $n^{O(d/\varepsilon^{2})}…
cs.LO2020
Relativization of Gurevich's Conjectures
Anatole Dahan, Anuj Dawar
Gurevich (1988) conjectured that there is no logic for or for . For the latter complexity class, he also showed that the existence of a…