34 citations · 111 across the 19 of their papers we have counts for
23 papers
When do homomorphism counts help in query algorithms?
Balder ten Cate, Víctor Dalmau, Phokion G. Kolaitis +1
A query algorithm based on homomorphism counts is a procedure for determining whether a given instance satisfies a property by counting homomorphisms between the given instance and…
Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes
Balder ten Cate, Víctor Dalmau, Jakub Opršal
A Datalog program can be viewed as a syntactic specification of a functor from database instances over some schema to database instances over another schema. The same holds more ge…
Functors on relational structures which admit both left and right adjoints
Víctor Dalmau, Andrei Krokhin, Jakub Opršal
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors and between thin categories of relational s…
Local consistency as a reduction between constraint satisfaction problems
Victor Dalmau, Jakub Opršal
We study the use of local consistency methods as reductions between constraint satisfaction problems (CSPs), and promise version thereof, with the aim to classify these reductions…
Extremal Fitting Problems for Conjunctive Queries
Balder ten Cate, Victor Dalmau, Maurice Funk +1
The fitting problem for conjunctive queries (CQs) is the problem to construct a CQ that fits a given set of labeled data examples. When a fitting CQ exists, it is in general not un…
Promise Constraint Satisfaction and Width
Albert Atserias, Víctor Dalmau
We study the power of the bounded-width consistency algorithm in the context of the fixed-template Promise Constraint Satisfaction Problem (PCSP). Our main technical finding is tha…