Zobrazeno 1 - 10
of 81
pro vyhledávání: '"Dalmau, Victor"'
We introduce the framework of the left-hand side restricted promise constraint satisfaction problem, which includes problems like approximating clique number of a graph. We study the parameterized complexity of problems in this class and provide some
Externí odkaz:
http://arxiv.org/abs/2402.06821
In this paper we study the interactions between so-called fractional relaxations of the integer programs (IPs) which encode homomorphism and isomorphism of relational structures. We give a combinatorial characterization of a certain natural linear pr
Externí odkaz:
http://arxiv.org/abs/2401.16998
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 finitely many predetermined instances. In a left query algorithm, we
Externí odkaz:
http://arxiv.org/abs/2304.06294
This paper describes several cases of adjunction in the homomorphism preorder of relational structures. We say that two functors $\Lambda$ and $\Gamma$ between thin categories of relational structures are adjoint if for all structures $\mathbf A$ and
Externí odkaz:
http://arxiv.org/abs/2302.13657
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 generally for $\exists$Datalog. We establish large classes of Datalog an
Externí odkaz:
http://arxiv.org/abs/2302.06366
Autor:
Dalmau, Victor, Opršal, Jakub
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 in a similar way as the algebraic approach classifies gadget reduction
Externí odkaz:
http://arxiv.org/abs/2301.05084
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 unique. This leads us to proposing natural refinements of the notion of
Externí odkaz:
http://arxiv.org/abs/2206.05080
Autor:
Atserias, Albert, Dalmau, Víctor
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 that the template of every PCSP that is solvable in bounded width satisfi
Externí odkaz:
http://arxiv.org/abs/2107.05886
Autor:
Butti, Silvia, Dalmau, Victor
Given a pair of graphs $\textbf{A}$ and $\textbf{B}$, the problems of deciding whether there exists either a homomorphism or an isomorphism from $\textbf{A}$ to $\textbf{B}$ have received a lot of attention. While graph homomorphism is known to be NP
Externí odkaz:
http://arxiv.org/abs/2107.02956
Autor:
Cate, Balder ten, Dalmau, Victor
We answer the question which conjunctive queries are uniquely characterized by polynomially many positive and negative examples, and how to construct such examples efficiently. As a consequence, we obtain a new efficient exact learning algorithm for
Externí odkaz:
http://arxiv.org/abs/2008.06824