Thursday, November 16, 2017 3:30 pm
-
3:30 pm
EST (GMT -05:00)
Renzhi Song, Department of Pure Mathematics, University of Waterloo
"Series parallel posets and polymorphisms, part 2"
In this two part series I will talk about the poset retraction problem on the class of series parallel posets. Having classified those series-parallel posets whose retraction problem can be solved in polynomial time, I will now show that these same posets admit what is known as SD-join polymorphisms. Equivalently, their retraction problems are in nondeterministic log space.
MC 5413