Algebra Seminar talk

Jakub Rydval
A long-standing meta problem at the core of the infinite-domain CSP dichotomy conjecture


The infinite-domain CSP dichotomy conjecture extends the recently proven finite-domain CSP dichotomy theorem to reducts of finitely bounded homogeneous structures. By Fraïssé's Theorem, finitely bounded homogeneous structures are in a one to one correspondence to universal sentences whose finite models form a class with the amalgamation property.

In this talk, I motivate a complexity-theoretic view on the classification problem for finitely bounded homogeneous structures. I provide several new lower bounds of ascending strength for the complexity of testing the amalgamation property for universal sentences under different restrictions on the input.