This file can be used to add scheduled events to your calendar, however every program is unique. Below you will find what information is available, but if nothing else works try creating a new calendar in your program and using
http://math.colorado.edu/seminars/ics/allo.ics
as the source.
Thunderbird
The Algebra and Logic seminar is a research and learning seminar organized by the algebra and logic research group of the Department of Mathematics at the University of Colorado at Boulder. The scope of the seminar includes all topics with links to algebra, logic, or their applications, like general algebra, logic, model theory, category theory, set theory, set-theoretic topology, or theoretical computer science. If you have questions regarding this seminar, please contact Keith Kearnes or Peter Mayr.
Tue, Apr. 7 1:25pm (MATH 2…
Nick Jamesson (CU Boulder)
X
The family of promise constraint satisfaction problems (PCSPs) is a variant of the well studied family of constraint satisfaction problems (CSPs). The computational problem of solving promise systems of equations over algebras is a variant of the problem of systems of equations over algebras. Given two algebras A and B of the same signature such that A maps homomorphically into B, one can ask if a system of equations has a solution in A or if it doesn't even have a solution in B. Given a finite algebra A, it is known that determining whether or not systems of equations over A have a solution is either solvable in polynomial time, or is NP complete (the famous dichotomy theorem for CSPs.) The question of whether or not a dichotomy holds for promise systems of equations over finite algebras is open in general. I will present some dichotomy results for promise systems of equations over various classes of algebras, including Mal'cev algebras.
Promise Systems Of Equations Over Finite Algebras
Tue, Apr. 14 1:25pm (MATH 2…
Sangman Lee (CU Boulder)
X
We study the subpower intersection problem (SIP) for a fixed finite semigroup S: given sets A,B of n-tuples A,B over S, decide whether the subsemigroups generated by A and B have nonempty intersection. We will present the following complexity results for SIP over finite semigroups. For every finite semigroup S, SIP(S) is in PSPACE. For finite bands, SIP(S) is in P if S is normal and is NP-complete otherwise. For full transformation semigroups T_n, SIP(T_2) is NP-complete and SIP(T_n) is PSPACE-complete for n > 2. For finite (completely) simple semigroups, SIP(S) is in P, and moreover SIP(S^1) is in P if S is a group and is NP-complete otherwise.
The subpower intersection problem for finite semigroups
In 2008, Bodirsky and Grohe showed that for every \Pi_n^P-level of the Polynomial Hierarchy (PH) there are omega-categorical Constraint Satisfaction Problems (CSPs) complete for this level. We show that, in fact, there are omega-categorical CSPs complete for any level of the PH. To this end, we use a recent result of Bodirsky, Kn\"{a}uer, and Rudolph for constructing omega-categorical CSPs from sentences of Monadic Second-Order logic (MSO) with certain preservation properties. As a secondary contribution, we develop a new tool for producing MSO sentences satisfying said preservation properties. In the present talk, I give an overview of the above-mentioned results and motivate several new questions. This is joint work with Santiago Guzman-Pro.
The polynomial hierarchy and omega-categorical CSPs
Promise Systems Of Equations Over Finite Algebras