Explanipedia

Functors on Relational Structures Which Admit Both Left and Right Adjoints Open

Víctor Dalmau, Andrei Krokhin, Jakub Opršal · 2024

Local consistency as a reduction between constraint satisfaction problems Open

Víctor Dalmau, Jakub Opršal · 2024

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 gadge…

The Complexity of Promise Constraint Satisfaction Problem Seen from the Other Side Open

Kristina Asimi, Libor Barto, Víctor Dalmau · 2024

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 p…

The Sherali-Adams and Weisfeiler-Leman hierarchies in (Promise Valued) Constraint Satisfaction Problems Open

Libor Barto, Silvia Butti, Víctor Dalmau · 2024

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 natura…

Extremal Fitting Problems for Conjunctive Queries Open

Balder ten Cate, Víctor Dalmau, Maurice Funk, Carsten Lutz · 2023

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…

When do homomorphism counts help in query algorithms? Open

Balder ten Cate, Víctor Dalmau, Phokion G. Kolaitis, Weilin Wu · 2023

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 alg…

Functors on relational structures which admit both left and right adjoints Open

Víctor Dalmau, Andrei Krokhin, Jakub Opršal · 2023

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 structures are adjoint if for all structures $\mathbf A$ and…

Right-Adjoints for Datalog Programs, and Homomorphism Dualities over Restricted Classes Open

Balder ten Cate, Víctor Dalmau, Jakub Opršal · 2023

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…

Local consistency as a reduction between constraint satisfaction problems Open

Víctor Dalmau, Jakub Opršal · 2023

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 gadge…

Conjunctive Queries: Unique Characterizations and Exact Learnability Open

Balder ten Cate, Víctor Dalmau · 2022

We answer the question of 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 a…

The Complexity of the Distributed Constraint Satisfaction Problem Open

Silvia Butti, Víctor Dalmau · 2022

We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with…

Extremal Fitting Problems for Conjunctive Queries Open

Balder ten Cate, Víctor Dalmau, Maurice Funk, Carsten Lutz · 2022

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…

Promise Constraint Satisfaction and Width Open

Albert Atserias, Víctor Dalmau · 2022

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 wi…

Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction Problem Open

Silvia Butti, Víctor Dalmau · 2021

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 kno…

Fractional homomorphism, Weisfeiler-Leman invariance, and the\n Sherali-Adams hierarchy for the Constraint Satisfaction Problem Open

Silvia Butti, Víctor Dalmau · 2021

Given a pair of graphs $\\textbf{A}$ and $\\textbf{B}$, the problems of\ndeciding whether there exists either a homomorphism or an isomorphism from\n$\\textbf{A}$ to $\\textbf{B}$ have received a lot of attention. While graph\nhomomorphism…

The Complexity of the Distributed Constraint Satisfaction Problem Open

Silvia Butti, Víctor Dalmau · 2021

We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with…

Conjunctive Queries: Unique Characterizations and Exact Learnability Open

Balder ten Cate, Víctor Dalmau · 2021

We answer the question of 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 …

Dismantlability, connectedness, and mixing in relational structures Open

Raimundo Briceño, Andreǐ A. Bulatov, Víctor Dalmau, Benoît Larose · 2020

Conjunctive Queries: Unique Characterizations and Exact Learnability Open

Balder ten Cate, Víctor Dalmau · 2020

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 alg…

The Complexity of the Distributed Constraint Satisfaction Problem Open

Silvia Butti, Víctor Dalmau · 2020

We study the complexity of the Distributed Constraint Satisfaction Problem (DCSP) on a synchronous, anonymous network from a theoretical standpoint. In this setting, variables and constraints are controlled by agents which communicate with…

The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs Open

Pablo Barceló, Víctor Dalmau, Cristina Feier, Carsten Lutz, Andréas Pieris · 2020

Ontology-mediated querying and querying in the presence of constraints are two key database problems where tuple-generating dependencies (TGDs) play a central role. In ontology-mediated querying, TGDs can formalize the ontology and thus de…

The Limits of Efficiency for Open- and Closed-World Query Evaluation\n Under Guarded TGDs Open

Pablo Barceló, Víctor Dalmau, Cristina Feier, Carsten Lutz, Andréas Pieris · 2019

Ontology-mediated querying and querying in the presence of constraints are\ntwo key database problems where tuple-generating dependencies (TGDs) play a\ncentral role. In ontology-mediated querying, TGDs can formalize the ontology\nand thus…

Dismantlability, Connectedness, and Mixing in Relational Structures Open

Raimundo Brice no, Andreǐ A. Bulatov, Víctor Dalmau, Benot Larose · 2019

The Constraint Satisfaction Problem (CSP) and its counting counterpart appears under different guises in many areas of mathematics, computer science, and elsewhere. Its structural and algorithmic properties have demonstrated to play a cruc…

Long range actions, connectedness, and dismantlability in relational structures. Open

Raimundo Briceño, Andreĭ A. Bulatov, Víctor Dalmau, Benoît Larose · 2019

In this paper we study alternative characterizations of dismantlability properties of relational structures in terms of various connectedness and mixing notions. We relate these results with earlier work of Brightwell and Winkler, providin…

Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs Open

Víctor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev , et al. · 2019

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of \nconstraints on overlapping sets of variables, and the goal is to assign values from a xed domain to \nthe variables so that all constraints are satised. In …

Towards a characterization of constant-factor approximable finite-valued CSPs Open

Víctor Dalmau, Andrei Krokhin, Rajsekar Manokaran · 2018

Conjunctions of Among Constraints Open

Víctor Dalmau · 2017

Many existing global constraints can be encoded as a conjunction of among constraints. An among constraint holds if the number of the variables in its scope whose value belongs to a prespecified set, which we call its range, is within some…

Robust algorithms with polynomial loss for near-unanimity CSPs Open

Víctor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev , et al. · 2017

An instance of the Constraint Satisfaction Problem \n(CSP) is given by a family of constraints on overlapping \nsets of variables, and the goal is to assign \nvalues from a fixed domain to the variables so that \nall constraints are satisf…

Towards a Characterization of Constant-Factor Approximable Finite-Valued\n CSPs Open

Víctor Dalmau, Andrei Krokhin, Rajsekar Manokaran · 2016

In this paper we study the approximability of (Finite-)Valued Constraint\nSatisfaction Problems (VCSPs) with a fixed finite constraint language {\\Gamma}\nconsisting of finitary functions on a fixed finite domain. An instance of VCSP\nis g…

Robust algorithms with polynomial loss for near-unanimity CSPs Open

Víctor Dalmau, Marcin Kozik, Andrei Krokhin, Konstantin Makarychev, Yury Makarychev , et al. · 2016

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In …

Víctor Dalmau YOU? Author Swipe