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
For a permutation group G on a set X, a mixed identity is an expression of the form w(x_1,...,x_n,g_1,...,g_m)=1, where w is a word in the language of groups with constants g_1,...,g_m from G and free variables x_1,...,x_n. We say that the mixed identity holds in G if substitution of arbitrary elements of G for the free variables yields a true statement. The mixed identity is singular if deletion of all constants yields a true statement in the free group: for example, xgx^{-1}=1 (where x is a variable and g a constant) is singular. We consider the question which non-singular mixed identities hold in a given group G. The group G is oligomorphic if it acts with finitely many orbits on X^n, for all n. Based on several examples, Bodirsky, Schneider, and Thom have conjectured that in oligomorphic groups only singular identities can hold. We confirm this conjecture for all oligomorphic G without algebraicity, i.e. with the property that for any tuple t of elements of X, the stabilizer of t in G does not stabilize any element outside t. In fact, we obtain this result under even more general conditions satisfied e.g. by the general linear group of any infinite vector space over a finite field. This is joint work with Paolo Marimon (Oxford).
Mixed identities in oligomorphic groups Sponsored by the Meyer Fund
We study constraint satisfaction problems (CSPs) where the constraint languages are defined by finite automata, giving rise to automata-based CSPs. The key notion is the concept of Automatic Constraint Satisfaction Problem ($\AutCSP$) where constraint languages and instances are specified by finite automata. The $\AutCSP$ captures infinite yet finitely describable sets of relations, enabling concise representations of complex constraints. Studying the complexity of the $\AutCSP$s illustrates the interplay between classical CSPs, automata, and logic, sharpening the boundary between tractable and intractable constraints. We show that checking whether an operation is a polymorphism of such a language can be done in polynomial time. Building on this, we establish several complexity classification results for the $\AutCSP$. In particular, we prove that Schaefer’s Dichotomy Theorem extends to the $\AutCSP$ over the Boolean domain, and we provide algorithms that decide tractability of some classes of $\AutCSP$s over arbitrary finite domains via automatic polymorphisms. An important part of our work is that our polynomial-time algorithms run on $\AutCSP$ instances that can be exponentially more succinct than their standard CSP counterparts.
Automatic constraint satisfaction problem Sponsored by the Meyer Fund
Promise Systems Of Equations Over Finite Algebras