Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > PROGRAMS OVER MONOIDS:
Reports tagged with Programs over Monoids:
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
model. When is a monoid rich enough that it can recognize arbitrary
languages (provided no restriction on length is imposed)? When ... more >>>

TR01-067 | 18th September 2001
Hubie Chen

#### Polynomial Programs and the Razborov-Smolensky Method

Representations of boolean functions as polynomials (over rings) have
been used to establish lower bounds in complexity theory. Such
representations were used to great effect by Smolensky, who
established that MOD q \notin AC^0[MOD p] (for distinct primes p, q)
by representing AC^0[MOD p] functions as low-degree multilinear
polynomials over ... more >>>

ISSN 1433-8092 | Imprint