10 citations · 37 across the 29 of their papers we have counts for
46 papers
Preservation Theorems in Semiring Semantics
Sophie Brinke, Anuj Dawar, Erich Grädel +1
We study the status of preservation theorems such as the Łoś-Tarski theorem and the homomorphism preservation theorem in the context of semiring semantics. Semiring semantics has i…
Logical aspects of isomorphism of controllable graphs and cospectrality of distance-regularized graphs
Aida Abiad, Anuj Dawar, Octavio B. Zapata-Fonseca
We consider isomorphism of controllable graphs and cospectrality of distance-regularized graphs (which are known to be distance-regular or distance-biregular) in relation to logica…
Complexity of Satisfiability in Kochen-Specker Partial Boolean Algebras
Anuj Dawar, Nihil Shah
The Kochen-Specker no-go theorem established that hidden-variable theories in quantum mechanics necessarily admit contextuality. This theorem is formally stated in terms of the par…
Arity hierarchies for quantifiers closed under partial polymorphisms
Anuj Dawar, Lauri Hella, Benedikt Pago
We investigate the expressive power of generalized quantifiers closed under partial polymorphism conditions motivated by the study of constraint satisfaction problems. We answer a…
Characterizing NC1 with Typed Monoids
Anuj Dawar, Aidan T. Evans
Krebs et al. (2007) gave a characterization of the complexity class TC0 as the class of languages recognized by a certain class of typed monoids. The notion of typed monoid was int…
Symmetric Proofs in the Ideal Proof System
Anuj Dawar, Erich Grädel, Leon Kullmann +1
We consider the Ideal Proof System (IPS) introduced by Grochow and Pitassi and pose the question of which tautologies admit symmetric proofs, and of what complexity. The symmetry r…