Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Group Theory:
TR01-040 | 16th May 2001
Pierre Péladeau, Denis Thérien

On the Languages Recognized by Nilpotent Groups (a translation of "Sur les Langages Reconnus par des Groupes Nilpotents")

We study a model of computation where executing a program on an input corresponds to calculating a product in a finite monoid. We show that in this model, the subsets of {0,1}^n that can be recognized by nilpotent groups have exponential cardinality.

Translator's note: This is a translation of the ... 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 >>>

TR10-051 | 26th March 2010
Madhu Sudan

Invariance in Property Testing

Property testing considers the task of testing rapidly (in particular, with very few samples into the data), if some massive data satisfies some given property, or is far from satisfying the property. For ``global properties'', i.e., properties that really depend somewhat on every piece of the data, one could ask ... more >>>

ISSN 1433-8092 | Imprint