109 citations · 130 across the 17 of their papers we have counts for
22 papers
Finite Algebras with Hom-Sets of Polynomial Size
Libor Barto, Antoine Mottet
We provide an internal characterization of those finite algebras (i.e., algebraic structures) such that the number of homomorphisms from any finite algebra …
Symmetries of structures that fail to interpret something finite
Libor Barto, Bertalan Bodor, Marcin Kozik +2
We investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters…
Weisfeiler-Leman Invariant Promise Valued CSPs
Libor Barto, Silvia Butti
In a recent line of work, Butti and Dalmau have shown that a fixed-template Constraint Satisfaction Problem is solvable by a certain natural linear programming relaxation (equivale…
Fixed-Template Promise Model Checking Problems
Kristina Asimi, Libor Barto, Silvia Butti
The fixed-template constraint satisfaction problem (CSP) can be seen as the problem of deciding whether a given primitive positive first-order sentence is true in a fixed structure…
Combinatorial Gap Theorem and Reductions between Promise CSPs
Libor Barto, Marcin Kozik
A value of a CSP instance is typically defined as a fraction of constraints that can be simultaneously met. We propose an alternative definition of a value of an instance and show…
Unifying the Three Algebraic Approaches to the CSP via Minimal Taylor Algebras
Libor Barto, Zarathustra Brady, Andrei Bulatov +2
This paper focuses on the algebraic theory underlying the study of the complexity and the algorithms for the Constraint Satisfaction Problem (CSP). We unify, simplify, and extend p…