The CSP dichotomy of Bulatov and Zhuk is a celebrated theorem of computer science: it states that given a finite structure $H$, deciding whether a structure $G$ admits a homomorphism to $G$ is either easy (in $P$) or hard ($NP$-complete).

We will discuss two infinitary versions of this theorem. First, following Thornton, in the Borel context. Here a striking difference from the finite world emerges: we will show that solving linear equations over a finite field is already hard ($\Sigma^1_2$-complete).

Second, assuming only ZF, we will consider the relationship of the $H$-compactness properties, that is, the statement that for every $G$ if every finite substructure of $G$ admits a homomorphism to $H$ then so is $G$. Here we show that there exists a model $M$ of ZF, such that $M \models H$-compactness iff the $H$-homomorphism problem is easy.

Joint works with Greb\'ik and K\'atay-T\'oth."