Universal Algebra Seminar

Thursday, January 14, 2016 2:30 pm - 2:30 pm EST (GMT -05:00)

Ian Payne, Department of Pure Mathematics, University of Waterloo

"A result on constraint satisfaction problems"

Over the next three or so lectures, I will explain a result that shows a certain class of constraint satisfaction problems is solvable in polynomial time. It is a generalization of a result of Andrei Bulatov regarding 2-semilattices. The result will almost surely not be mentioned until the second lecture. The first lecture will be an introduction to the version of CSP I will be addressing. I will be assuming some universal algebra, but for the first lecture I will only need basic definitions. For example, you won't get lost if you don't know what a 2-semilattice is.

MC 5403