Pierre Péladeau, Denis Thérien

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

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

Madhu Sudan

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