Michael Pinsker – Smooth approximations in oligomorphic clones

Vienna University of Technology
We present the novel method of smooth approximations which allows us to extract information about an oligomorphic clone from an appropriate subclone. This yields in turn a structural dichotomy for certain oligomorphic clones: either they are equationally “simple", or there is a witness of finite character for their non-simplicity. Applying this to constraint satisfaction problems, we obtain complexity classifications for various classes of omega-categorical structures.

(Joint work with A. Mottet)