Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Denis Thérien:

TR06-117 | 31st August 2006
Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

Languages with Bounded Multiparty Communication Complexity

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 >>>

TR05-059 | 9th May 2005
Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

Tractable Clones of Polynomials over Semigroups

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 >>>

TR04-091 | 29th September 2004
Ondrej Klíma, Pascal Tesson, Denis Thérien

Dichotomies in the Complexity of Solving Systems of Equations over Finite Semigroups

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 >>>

TR01-040 | 16th May 2001
Pierre Péladeau, Denis Thérien

On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality.

Translator's note: This is a translation of the ... more >>>

TR01-005 | 27th October 2000
Pascal Tesson, Denis Thérien

The Computing Power of Programs over Finite Monoids

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 >>>

ISSN 1433-8092 | Imprint