8 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…
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 celebrate…
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…
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…
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…
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…