Caltech Logo

Logic Seminar

Wednesday, September 22, 2021
12:00pm to 1:00pm
Add to Cal
Online Event
An algebraic approach to Borel CSPs
Riley Thornton, Department of Mathematics, UCLA,

For a given finite relational structure R, the associated constraint satisfaction problem (or CSP) is the problem of testing when a structure admits a homomorphism into R. The algebraic approach studies a CSP by considering its algebra of so-called polymorphisms, operations (of all arities) which preserve the relations in R. This approach has led to many classification results. For instance, CSPs solvable by polynomial time algorithms, linear relaxation, and constraint propagation have all been classified. In this talk I will present partial results towards similar classifications of Borel CSPs with various descriptive set theoretic properties: those problems which are Π11 in the codes, effectivizable, or equivalent to their classical version.

For more information, please email A. Kechris at kechris@caltech.edu.