A fundamental fact for the algebraic theory of constraint satisfaction problems (CSPs) over a
fixed template is that pp-interpretations between at most countable ω-categorical relational …

Schaefer's theorem is a complexity classification result for so-called Boolean constraint
satisfaction problems: it states that every Boolean constraint satisfaction problem is either …

We prove that an ω-categorical core structure primitively positively interprets all finite
structures with parameters if and only if some stabilizer of its polymorphism clone has a …

It is known that a countable-categorical structure interprets all finite structures primitively
positively if and only if its polymorphism clone maps to the clone of projections on a two …

The tractability conjecture for finite domain constraint satisfaction problems (CSPs) stated
that such CSPs are solvable in polynomial time whenever there is no natural reduction, in …

There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely
bounded homogeneous structures: the first one states that tractability of the CSP of such a …

For n≧3, let (H_n,E) denote the n th Henson graph, ie, the unique countable homogeneous
graph with exactly those finite graphs as induced subgraphs that do not embed the complete …

We introduce the novel machinery of smooth approximations, and apply it to confirm the
CSP dichotomy conjecture for first-order reducts of the random tournament, and to give new …

We systematically study the computational complexity of a broad class of computational
problems in phylogenetic reconstruction. The class contains, for example, the rooted triple …

We study the complexity of infinite-domain constraint satisfaction problems (CSPs): our basic
setting is that a complexity classification for the CSPs of first-order expansions of a structure …