10 citations · 12 across the 11 of their papers we have counts for
5 papers · 1 filter
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…
Undefinability of Approximation of 2-to-2 Games
Anuj Dawar, Bálint Molnár
Recent work by Atserias and Dawar (J. Log. Comp 2019) and Tucker-Foltz (LMCS 2024) has established undefinability results in fixed-point logic with counting (FPC) corresponding to…
Symmetric Algebraic Circuits and Homomorphism Polynomials
Anuj Dawar, Benedikt Pago, Tim Seppelt
The central open question of algebraic complexity is whether VP is unequal to VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic…