Inici
→
Recerca: articles, congressos, llibres
→
Departament de Tecnologies de la Informació i les Comunicacions
→
Visualitza Departament de Tecnologies de la Informació i les Comunicacions per autoria

Visualitza Departament de Tecnologies de la Informació i les Comunicacions per autoria "Dalmau, Víctor"

Ara mostrant els elements 1-17 de 17

A combinatorial characterization of resolution width

Atserias, Albert; Dalmau, Víctor (Elsevier, 2008)

We provide a characterization of the resolution width introduced in the context of propositional proof complexity in terms of the existential pebble game introduced in the context of finite model theory. The characterization ...
Conjunctive queries: unique characterizations and exact learnability

ten Cate, Balder; Dalmau, Víctor (Dagstuhl Publishing, 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 ...
CSP duality and trees of bounded pathwidth

Carvalho, Catarina; Dalmau, Víctor; Krokhin, Andrei (Elsevier, 2010)

We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of ...
Datalog and constraint satisfaction with infinite templates

Bodirsky, Manuel; Dalmau, Víctor (Elsevier, 2013)

On finite structures, there is a well-known connection between the expressive power of Datalog, finite variable logics, the existential pebble game, and bounded hypertree duality. We study this connection for infinite ...
Dismantlability, connectedness, and mixing in relational structures

Briceño, Raimundo; Bulatov, Andrei A.; Dalmau, Víctor; Larose, Benoit (Elsevier, 2021)

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 been shown ...
Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the constraint satisfaction problem

Butti, Silvia; Dalmau, Víctor (Dagstuhl Publishing, 2021)

Given a pair of graphs 𝐀 and 𝐁, the problems of deciding whether there exists either a homomorphism or an isomorphism from 𝐀 to 𝐁 have received a lot of attention. While graph homomorphism is known to be NP-complete, ...
Learning intersection-closed classes with signatures

Bulatov, Andrei A.; Chen, Hubie; Dalmau, Víctor (Elsevier, 2007)

Intersection-closed classes of concepts arise naturally in many contexts and have been intensively studied in computational learning theory. In this paper, we study intersection-closed classes that contain the concepts ...
Majority constraints have bounded pathwidth duality

Dalmau, Víctor; Krokhin, Andrei (Elsevier, 2008)

We study certain constraint satisfaction problems which are the problems of deciding whether there exists a homomorphism from a given relational structure to a fixed structure with a majority polymorphism. We show that ...
Phase transitions of PP-complete satisfiability problems

Bailey, Delbert D.; Dalmau, Víctor; Kolaitis, Phokion G. (Elsevier, 2007)

The complexity class PP consists of all decision problems solvable by polynomial-time probabilistic Turing machines. It is well known that PP is a highly intractable complexity class and that PP-complete problems are in ...
Promise constraint satisfaction and width

Atserias, Albert; Dalmau, Víctor (SIAM (Society for Industrial and Applied Mathematics), 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 ...
Regularizing conjunctive features for classification

Barceló, Pablo; Baumgartner, Alexander; Dalmau, Víctor; Kimelfeld, Benny (Elsevier, 2021)

We consider the feature-generation task wherein we are given a database with entities labeled as positive and negative examples, and we want to find feature queries that linearly separate the two sets of examples. We focus ...
Retractions onto series-parallel posets

Dalmau, Víctor; Krokhin, Andrei; Larose, Benoit (Elsevier, 2008)

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study ...
Robust algorithms with polynomial loss for near-unanimity CSPs

Dalmau, Víctor; Kozik, Marcin; Krokhin, Andrei; Makarychev, Konstantin; Makarychev, Yury; Opršal, Jakub (SIAM (Society for Industrial and Applied Mathematics), 2019)

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 ...
The complexity of the distributed constraint satisfaction problem

Butti, Silvia; Dalmau, Víctor (SpringerOpen, 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 ...
Towards a characterization of constant-factor approximable finite-valued CSPs

Dalmau, Víctor; Krokhin, Andrei; Manokaran, Rajsekar (Elsevier, 2018)

We study the approximability of (Finite-)Valued Constraint Satisfaction Problems (VCSPs) with a fixed finite constraint language Γ consisting of finitary functions on a fixed finite domain. Ene et al. have shown that, under ...
Towards a characterization of constant-factor approximable Min CSPs

Dalmau, Víctor; Krokhin, Andrei; Manokaran, Rajsekar (SIAM (Society for Industrial and Applied Mathematics), 2015)

We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied ...
Towards a dichotomy theorem for the counting constraint satisfaction problem

Bulatov, Andrei A.; Dalmau, Víctor (Elsevier, 2007)

The Counting Constraint Satisfaction Problem (#CSP) can be expressed as follows: given a set of variables, a set of values that can be taken by the variables, and a set of constraints specifying some restrictions on the ...