We present algebraic conditions on constraint languages \Gamma that ensure the hardness of the constraint satisfaction problem CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP(\Gamma) is not first-order definable then it ... more >>>

We present algebraic conditions on constraint languages \Gamma that ensure the hardness of the constraint satisfaction problem CSP(\Gamma) for complexity classes L, NL, P, NP and Mod_pL. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP(\Gamma) is not first-order definable then it ... more >>>

We introduce symmetric Datalog, a syntactic restriction of linear Datalog and show that its expressive power is exactly that of restricted symmetric monotone Krom SNP. The deep result of Reingold on the complexity of undirected connectivity suffices to show that symmetric Datalog queries can be evaluated in logarithmic space. We ... more >>>

We study languages with bounded communication complexity in the multiparty "input on the forehead" model with worst-case partition. In the two party case, it is known that such languages are exactly those that are recognized by programs over commutative monoids. This can be used to show that these languages can ... more >>>

It is well known that coset-generating relations lead to tractable constraint satisfaction problems. These are precisely the relations closed under the operation $xy^{-1}z$ where the multiplication is taken in some finite group. Bulatov et al. have on the other hand shown that any clone containing the multiplication of some ``block-group'' ... more >>>

We consider the problem of testing whether a given system of equations over a fixed finite semigroup S has a solution. For the case where S is a monoid, we prove that the problem is computable in polynomial time when S is commutative and is the union of its subgroups ... more >>>

The formalism of programs over monoids has been studied for its close connection to parallel complexity classes defined by small-depth boolean circuits. We investigate two basic questions about this model. When is a monoid rich enough that it can recognize arbitrary languages (provided no restriction on length is imposed)? When ... more >>>