Browsing by Author "Dalmau, Víctor"

Sort by: Order: Results:

  • 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 ...
  • 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 ...
  • 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 ...
  • Bulatov, Andrei; 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...
  • 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 ...