Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > VÍCTOR DALMAU:
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

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


TR04-097 | 2nd November 2004
Víctor Dalmau

Malt'sev Constraints made Simple

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

more >>>

TR02-035 | 27th May 2002
Albert Atserias, Víctor Dalmau

A Combinatorial Characterization of Resolution Width

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




ISSN 1433-8092 | Imprint