Warning

You must use an API key to authenticate each request to Google Maps Platform APIs. For additional information, please refer to http://g.co/dev/maps-no-account

Model theory seminar, James Rooney, McMaster

Description


Title: An Exploration into the Mal'tsev Condition Satisfaction Problem for various Mal'tsev Conditions

Abstract: This talk will serve as a brief tour of one particular small and complicated region of the Complexity Zoo which became the subject of my PhD Thesis. It was once conjectured that the satisfaction of linear strong Mal'tsev conditions should be easy to check (for idempotent algebras) while nonlinear strong Mal'tsev conditions would likely remain hard even in the idempotent case. In this talk I will introduce Mal'tsev Condition Satisfaction Problems and describe some important results in my thesis which explore the conjecture described above. In particular, we will show that checking the satisfaction of "height <1" strong Mal'tsev conditions in idempotent algebras is not that hard (read: in NP)- providing limited evidence that half of the conjecture could still be valid - and that checking the satisfaction of some nonlinear Mal'tsev conditions is also not that hard - providing evidence that this region of the Complexity Zoo is not as easy to navigate as the original conjecture was hoping for. The talk is intended for an audience of interested logicians and assumes no background knowledge of Mal'tsev conditions or related topics in Universal Algebra. All the relevant definitions will be included.

Location information

Go Back
McMaster University - Faculty of Science | Math & Stats