Date:  24/08/06
 Speaker: Victor Dalmau
 Affiliation: Universitat Pompeu Fabra
 Title: Constraint Satisfaction, Logic, and Dualities.
 Abstract:
 For every relational structure B, the (non-uniform) constraint satisfaction problem associated to B, CSP(B), is the following computational problem: given a relational structure A, is there a homomorphism from A to B?. The complexity of the problem CSP(B) varies depending on the election of the structure B. In the last few years much effort has been invested in the project of classifying the computational complexity of CSP(B), for every B. An useful tool in this study has been the consideration of the logics that can express CSP(B). Perhaps the best illustration of this approach is the fact that a good number of the tractable cases of the problem identified so far can be explained, in an uniform way, as those CSP(B) definable in Datalog. In this talk we shall consider three logics that have been considered in the study of constraint satisfaction: datalog, linear datalog, and first-order logic. In the realm of CSP, each one of these logics has a counterpart in the form of dualities. In this talk we shall survey this connection. We shall discuss also the problem of deciding whether a given CSP(B) is definable in each one of these logics.

A talk at SFU in Canada