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

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