We consider CSPs whose template can be defined in an infinite “ground structure” with a high degree of symmetry (in the form of homogeneity) and a certain finite presentation (finite boundedness). For example, the ground structure can be the order of the rationals, leading to Temporal CSPs, or the random graph, which gives rise to so-called Graph-SAT problems. Such CSPs are always in NP, include all finite-domain CSPs as well as many additional natural problems, and there is an open dichotomy conjecture extending the one for finite templates.

The general algebraic approach to finite domain CSPs via polymorphisms
also works in this setting, and the most sensible approach to the
conjecture is to try to reduce it to the finite case. To this end, one
associates certain finite algebras to a CSP template, and hopes to
extract from them sufficient information about the complexity of the
CSP. In most successful confirmations of instances of the conjecture
so far, this was done somewhat non-systematically, leading to long
proofs of ad hoc arguments. The novel *Theory of Smooth Approximations*
intends to provide a uniform way of relating the associated finite
algebras with the structure of the CSP template and consequently its
computational complexity. Applying this method, all previous results
in the literature can be reproven much more smoothly; moreover, the
method allows, for the first time, for a systematic investigation of
local consistency methods in this setting.

This is joint work with Antoine Mottet.