research
∙
04/13/2023
When do homomorphism counts help in query algorithms?
A query algorithm based on homomorphism counts is a procedure for determ...
share
research
∙
02/27/2023
Functors on relational structures which admit both left and right adjoints
This paper describes several cases of adjunction in the homomorphism ord...
research
∙
02/13/2023
Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes
A Datalog program can be viewed as a syntactic specification of a functo...
research
∙
01/12/2023
Local consistency as a reduction between constraint satisfaction problems
We study the use of local consistency methods as reductions between cons...
research
∙
06/10/2022
Extremal Fitting Problems for Conjunctive Queries
The fitting problem for conjunctive queries (CQs) is the problem to cons...
research
∙
07/13/2021
Promise Constraint Satisfaction and Width
We study the power of the bounded-width consistency algorithm in the con...
research
∙
07/07/2021
Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem
Given a pair of graphs A and B, the problems of deciding whether there e...
research
∙
08/16/2020
Conjunctive Queries: Unique Characterizations and Exact Learnability
We answer the question which conjunctive queries are uniquely characteri...
research
∙
07/27/2020
The Complexity of the Distributed Constraint Satisfaction Problem
We study the complexity of the Distributed Constraint Satisfaction Probl...
research
∙
12/28/2019
The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs
Ontology-mediated querying and querying in the presence of constraints a...
research
∙
01/14/2019
Long range actions, connectedness, and dismantlability in relational structures
In this paper we study alternative characterizations of dismantlability ...
research
∙
06/15/2017
Conjunctions of Among Constraints
Many existing global constraints can be encoded as a conjunction of amon...
research
∙
04/26/2011