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

Hubie Chen

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