Evaluation properties of invariant polynomials

A polynomial invariant under the action of a finite group can be rewritten using generators of the invariant ring. We investigate the complexity aspects of this rewriting process; we show that evaluation techniques enable one to reach a polynomial cost.