Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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