Mottet, AntoineAntoineMottet2024-02-292024-02-29202432nd EACSL Annual Conference on Computer Science Logic (CSL 2024). - Wadern, 2024. - (Leibniz International Proceedings in Informatics, LIPIcs ; 288): - Art. 41978-3-95977-310-2https://hdl.handle.net/11420/46127Two particularly active branches of research in constraint satisfaction are the study of promise constraint satisfaction problems (PCSPs) with finite templates and the study of infinite-domain constraint satisfaction problems with ω-categorical templates. In this paper, we explore some connections between these two hitherto unrelated fields and describe a general approach to studying the complexity of PCSPs by constructing suitable infinite CSP templates. As a result, we obtain new characterizations of the power of various classes of algorithms for PCSPs, such as first-order logic, arc consistency reductions, and obtain new proofs of the characterizations of the power of the classical linear and affine relaxations for PCSPs.enfirst-order logichomogeneous structurespolymorphismspromise constraint satisfaction problemsComputer SciencesMathematicsConference Paper10.4230/LIPIcs.CSL.2024.41Conference Paper