Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction

Abstract

The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain well-behaved infinite templates due to Bodirsky and Pinsker which remains wide open. In this talk, I motivate several fundamental questions on the scope of the Bodirsky-Pinsker conjecture and provide answers to some of them. This concerns, e.g., identifying model-theoretic assumptions that can be added without loss of generality or finding general connections to finite-domain promise CSPs. The presented material stems from joint work with Michael Pinsker, Moritz Schöbi, and Christoph Spiess.