10 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…
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…
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…
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…
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…
Towards the type safety of Pure Subtype Systems (Full version)
Valentin Pasquale, Ãlvaro GarcÃa-Pérez
Hutchins' Pure Subtype Systems (PSS) offer a unified framework for types and terms, promising significant advancements in language design for features like dependent types and high…