All reports by Author Víctor Dalmau:

__
TR05-059
| 9th May 2005
__

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien#### Tractable Clones of Polynomials over Semigroups

__
TR04-097
| 2nd November 2004
__

Víctor Dalmau#### Malt'sev Constraints made Simple

__
TR02-035
| 27th May 2002
__

Albert Atserias, Víctor Dalmau#### A Combinatorial Characterization of Resolution Width

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

It is well known that coset-generating relations lead to tractable

constraint satisfaction problems. These are precisely the relations closed

under the operation $xy^{-1}z$ where the multiplication is taken in

some finite group. Bulatov et al. have on the other hand shown that

any clone containing the multiplication of some ``block-group'' ...
more >>>

Víctor Dalmau

We give in this paper a different and simpler proof of the tractability of Mal'tsev contraints.

more >>>Albert Atserias, Víctor Dalmau

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

is tight and purely combinatorial. Our

first application of this result is a surprising

proof that the ...
more >>>