Algebra Seminar talk
2022-11-25
Jakub Rydval
A long-standing meta problem at the core of the infinite-domain CSP dichotomy conjecture
Abstract:
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.