5 citations · 10 across the 6 of their papers we have counts for
13 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…
Optimal Lower Bounds for Symmetric Modular Circuits
Benedikt Pago
A notorious open question in circuit complexity is whether Boolean operations of arbitrary arity can efficiently be expressed using modular counting gates only. Håstad's celebrated…
Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
Prateek Dwivedi, Benedikt Pago, Tim Seppelt
Valiant's conjecture asserts that the circuit complexity classes VP and VNP are distinct, meaning that the permanent does not admit polynomial-size algebraic circuits. As it is the…
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…
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…
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…
Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
Moritz Lichter, Benedikt Pago
We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tract…
Choiceless Computation and Symmetry: Limitations of Definability
Benedikt Pago
The search for a logic capturing PTIME is a long standing open problem in finite model theory. One of the most promising candidate logics for this is Choiceless Polynomial Time wit…
Limitations of Game Comonads via Homomorphism Indistinguishability
Moritz Lichter, Benedikt Pago, Tim Seppelt
Abramsky, Dawar, and Wang (2017) introduced the pebbling comonad for k-variable counting logic and thereby initiated a line of work that imports category theoretic machinery to fin…
Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits
Benedikt Pago
Choiceless Polynomial Time (CPT) is one of the few remaining candidate logics for capturing PTIME. In this paper, we make progress towards separating CPT from polynomial time by fi…
Finite Model Theory and Proof Complexity revisited: Distinguishing graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus
Benedikt Pago
This paper extends prior work on the connections between logics from finite model theory and propositional/algebraic proof systems. We show that if all non-isomorphic graphs in a g…
Choiceless Polynomial Time, Symmetric Circuits and Cai-Fürer-Immerman Graphs
Benedikt Pago
Choiceless Polynomial Time (CPT) is currently the only candidate logic for capturing PTIME (that is, it is contained in PTIME and has not been separated from it). A prominent examp…
A Finite-Model-Theoretic View on Propositional Proof Complexity
Erich Grädel, Martin Grohe, Benedikt Pago +1
We establish new, and surprisingly tight, connections between propositional proof complexity and finite model theory. Specifically, we show that the power of several propositional…