10 citations · 12 across the 5 of their papers we have counts for
11 papers · 1 filter
Descriptive complexity of the generalized spectra of graphs
Aida Abiad, Anuj Dawar, Octavio Zapata
Two graphs are cospectral if their respective adjacency matrices have the same multiset of eigenvalues, and generalized cospectral if they are cospectral and so are their complemen…
Separating LREC from LFP
Anuj Dawar, Felipe Ferreira Santos
LREC= is an extension of first-order logic with a logarithmic recursion operator. It was introduced by Grohe et al. and shown to capture the complexity class L over trees and inter…
On the relative power of algebraic approximations of graph isomorphism
Anuj Dawar, Danny Vagnozzi
We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the \emph{invertible map tests} (introduced by Dawar and Holm) and…
Extension Preservation in the Finite and Prefix Classes of First Order Logic
Anuj Dawar, Abhisekh Sankaran
It is well known that the classic Łoś-Tarski preservation theorem fails in the finite: there are first-order definable classes of finite structures closed under extensions which ar…
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…
Approximations of Isomorphism and Logics with Linear-Algebraic Operators
Anuj Dawar, Erich Grädel, Wied Pakusa
Invertible map equivalences are approximations of graph isomorphism that refine the well-known Weisfeiler-Leman method. They are parametrised by a number k and a set Q of primes. T…