All reports by Author Pascal Tesson:

__
TR07-025
| 5th March 2007
__

Benoit Larose, Pascal Tesson, Pascal Tesson#### Universal Algebra and Hardness Results for Constraint Satisfaction Problems

__
TR07-025
| 5th March 2007
__

Benoit Larose, Pascal Tesson, Pascal Tesson#### Universal Algebra and Hardness Results for Constraint Satisfaction Problems

__
TR07-024
| 5th March 2007
__

Laszlo Egri, Benoit Larose, Pascal Tesson#### Symmetric Datalog and Constraint Satisfaction Problems in Logspace

__
TR06-117
| 31st August 2006
__

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien#### Languages with Bounded Multiparty Communication Complexity

__
TR05-059
| 9th May 2005
__

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien#### Tractable Clones of Polynomials over Semigroups

__
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

__
TR01-005
| 27th October 2000
__

Pascal Tesson, Denis Thérien#### The Computing Power of Programs over Finite Monoids

Benoit Larose, Pascal Tesson, Pascal Tesson

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

Benoit Larose, Pascal Tesson, Pascal Tesson

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

Laszlo Egri, Benoit Larose, Pascal Tesson

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

Arkadev Chattopadhyay, Michal Koucky, Andreas Krebs, Mario Szegedy, Pascal Tesson, Denis Thérien

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

Víctor Dalmau, Ricard Gavaldà, Pascal Tesson, Denis Thérien

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

Ondrej Klíma, Pascal Tesson, Denis Thérien

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

Pascal Tesson, Denis Thérien

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