Welcome to the UPF Digital Repository

Browsing Articles (Departament de Tecnologies de la Informació i les Comunicacions) by Author "Dalmau, Víctor"

Browsing Articles (Departament de Tecnologies de la Informació i les Comunicacions) by Author "Dalmau, Víctor"

Sort by: Order: Results:

  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 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 ...

Search DSpace


Advanced Search

Browse

My Account

In collaboration with Compliant to Partaking