BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Thomas-Quinn Gregson (TU Dresden)
DTSTART:20201014T103000Z
DTEND:20201014T113000Z
DTSTAMP:20260423T011102Z
UID:YSseminar/7
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/YSseminar/7/
 ">Solving equation systems in omega-categorical algebras</a>\nby Thomas-Qu
 inn Gregson (TU Dresden) as part of York semigroup seminar\n\n\nAbstract\n
 We study the computational complexity of deciding whether a given set of t
 erm equalities and inequalities has a solution in an omega-categorical alg
 ebra $A$. There are omega-categorical groups where this problem is undecid
 able. We show that if $A$ is an omega-categorical semilattice or an abelia
 n group\, then the problem is in P or NP-hard. The hard cases are precisel
 y those where $Pol(A\,\\neq)$ is ``small'' (has a uniformly continuous min
 or-preserving map to the clone of projections on a two-element set). We re
 ly on the Barto-Pinsker theorem about the existence of pseudo-Siggers poly
 morphisms. To the best of our knowledge\, this is the first time that the 
 pseudo-Siggers identity has been used to prove a complexity dichotomy.\n
LOCATION:https://researchseminars.org/talk/YSseminar/7/
END:VEVENT
END:VCALENDAR