Evaluating symmetric polynomials Let $f:\mathbb{K}^n \to \mathbb{K}$ be a symmetric polynomial, i.e., a polynomial such that $f(x)=f(\sigma(x))$ for all $x \in \mathbb{K}^n$ and all permutations $\sigma \in S_n$.  For convenience, we can assume $\mathbb{K}$ is a finite field, to avoid addressing issues with the model of computation.

Let $C(f)$ denote the complexity of computing $f$, i.e., the complexity of an algorithm that, given $x$, returns $f(x)$.  Can we somehow characterize $C(f)$, based on the properties of $f$?  For instance, are we guaranteed that $C(f)$ is polynomial (in $n$) for all symmetric polynomials $f$?

As special case, it looks like (a) we can compute the power sum polynomials in time $\text{poly}(n)$, and (b) we can compute the elementary symmetric polynomials in time $\text{poly}(n)$, using Newton's identities.  As a consequence, if $f$ is a weighted sum of monomials where no variable is raised to a power higher than 1 (i.e., if $f$ is multilinear), then $f$ can be computed in polynomial time (since it can be expressed as a weighted sum of elementary symmetric polynomials).  For instance, when $\mathbb{K}=GF(2)$, then every symmetric polynomial can be computed in polynomial time.  Can one say anything more than this?
The question seems quite open ended. Or perhaps you wish to have a precise characterization of the time-complexity of any possible symmetric polynomial over finite fields?

In any case, at least to my knowledge, there are several well-known results about the time-complexity of computing symmetric polynomials: 


If $f$ is an elementary symmetric polynomial over a finite field then it can be computed by polynomial-size uniform $TC^0$ circuits.
If $f$ is an elementary symmetric polynomial over a characteristic $0$ field, then it can be computed by polynomial-size depth three uniform algebraic circuits (as you already mentioned the Newton polynomial; or by the Lagrange interpolation formula); and so I believe this then translates to polynomial-size uniform Boolean circuits (though perhaps not of constant depth) (but this may depend on the specific field you're working in; for simplicity you might consider the ring of integers; though for the integers I presume $TC^0$ is enough to compute symmetric polynomials in any case.)
If $f$ is a symmetric polynomial over a finite field then there is an exponential lower bound on depth three algebraic circuits for $f$ (by Grigoriev and Razborov (2000) [following Grigoriev and Karpinsky 1998]). But, as mentioned in 1 above, this corresponds only to constant-depth Boolean circuit lower bounds (while there are small uniform Boolean circuits in $TC^0$; meaning also that the polynomials are computable in polynomial-time).  


Probably there are more known results about the time-complexity of symmetric polynomial...