Graduate student colloquium

Ian Payne, Pure Mathematics, University of Waterloo

"I Can't Get No (Constraint) Satisfaction"

The objective of this talk is to introduce the audience to the constraint satisfaction problem, or CSP. This broad class of decision problems was motivated by theoretical computer science, but is of interest to mathematicians since universal algebra is the main tool used in the study of their complexity. I will define relational structures, which give the framework for the CSP. Then give some examples, and state some of the important results in the area. Although I won't officially say anything about universal algebra, I will give an intuitive description of the connection between algebra and CSPs. The only knowledge I will assume is that of basic set theory. There will likely be some jokes, hopefully not including the talk itself.