<p>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?</p>

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

<ol>
<li><p>If $f$ is an elementary symmetric polynomial over a finite field then it can be computed by polynomial-size uniform $TC^0$ circuits.</p></li>
<li><p>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.)</p></li>
<li><p>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 <em>there are</em> small uniform Boolean circuits in $TC^0$; meaning also that the polynomials are computable in polynomial-time).  </p></li>
</ol>

<p>Probably there are more known results about the time-complexity of symmetric polynomial...</p>

CC BY-SA 3.0
2015-12-22T17:14:56.197Z
2015-12-24T17:09:15.453Z
2015-12-24T17:09:15.453Z
Iddo Tzameret
<p>Let $f:\mathbb{K}^n \to \mathbb{K}$ be a <a href="https://en.wikipedia.org/wiki/Symmetric_polynomial">symmetric polynomial</a>, 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.</p>

<p>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$?</p>

<p>As special case, it looks like (a) we can compute the <a href="https://en.wikipedia.org/wiki/Power_sum_symmetric_polynomial">power sum polynomials</a> in time $\text{poly}(n)$, and (b) we can compute the <a href="https://en.wikipedia.org/wiki/Elementary_symmetric_polynomial">elementary symmetric polynomials</a> in time $\text{poly}(n)$, using <a href="https://en.wikipedia.org/wiki/Newton&#39;s_identities">Newton's identities</a>.  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?</p>

CC BY-SA 3.0
2015-12-21T21:59:15.197Z
If you are interested in computation over $\mathbb{R}$ you may want to clarify the model of computation.
Kaveh
CC BY-SA 3.0
2015-12-22T00:49:08.703Z
@Kaveh, ahh, excellent point.  I guess I'm not super-focused on any one field, so I suppose I'll ask about finite fields to make that issue go away.  I'm more interested about whether there are results or systematic techniques for determining the complexity of evaluating a symmetric polynomial $f$.
D.W.
CC BY-SA 3.0
2015-12-22T02:11:46.093Z
How is f specified? This is crucial to the complexity of evaluation.
Thomas Steinke
CC BY-SA 3.0
2015-12-22T02:17:48.827Z
@Thomas, It shouldn't matter.  For any single fixed $f$, $C(f)$ is well-defined (it is the complexity of the best algorithm for computing $f$).  This is well-defined and doesn't depend on how $f$ is "specified".  (Note that $f$ is not an input to the algorithm, so its representation doesn't need to be defined.)  Or, to put it another way: if I have a symmetric function $f$ I want to compute, are there any techniques or results to help me find an efficient algorithm to compute $f$ or to determine how efficiently my $f$ can be computed?
D.W.
CC BY-SA 3.0
2015-12-22T02:21:23.487Z
I see. Can we assume an upper bound on the degree of f? or some other bound on its complexity.
Thomas Steinke
CC BY-SA 3.0
2015-12-22T02:47:02.297Z
@Thomas, yeah: if there are results or techniques that are applicable when the degree is not too large, that sounds useful.  (For instance, if the degree wrt to each variable, considered separately, is at most some small constant $c$, can we say something?  The last paragraph of my question handles the case $c=1$; can we say more?  Or, alternatively, if the total degree of $f$ is not too large, can we say something?)
D.W.
<cc.complexity-theory><permutations><polynomials>
Evaluating symmetric polynomials
D.W.
# Evaluating symmetric polynomials

(Asked by: username_0 on 2015-12-21)

Let $f:\mathbb{K}^n \to \mathbb{K}$ be a [symmetric polynomial](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/Power_sum_symmetric_polynomial) in time $\text{poly}(n)$, and (b) we can compute the [elementary symmetric polynomials](https://en.wikipedia.org/wiki/Elementary_symmetric_polynomial) in time $\text{poly}(n)$, using [Newton's identities](https://en.wikipedia.org/wiki/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?

**Tags:** cc.complexity-theory, permutations, polynomials
> **Comments:**
> **username_1**: If you are interested in computation over $\mathbb{R}$ you may want to clarify the model of computation.  
> **username_0**: @Kaveh, ahh, excellent point.  I guess I'm not super-focused on any one field, so I suppose I'll ask about finite fields to make that issue go away.  I'm more interested about whether there are results or systematic techniques for determining the complexity of evaluating a symmetric polynomial $f$.  
> **username_2**: How is f specified? This is crucial to the complexity of evaluation.  
> **username_0**: @Thomas, It shouldn't matter.  For any single fixed $f$, $C(f)$ is well-defined (it is the complexity of the best algorithm for computing $f$).  This is well-defined and doesn't depend on how $f$ is "specified".  (Note that $f$ is not an input to the algorithm, so its representation doesn't need to be defined.)  Or, to put it another way: if I have a symmetric function $f$ I want to compute, are there any techniques or results to help me find an efficient algorithm to compute $f$ or to determine how efficiently my $f$ can be computed?  
> **username_2**: I see. Can we assume an upper bound on the degree of f? or some other bound on its complexity.  
> **username_0**: @Thomas, yeah: if there are results or techniques that are applicable when the degree is not too large, that sounds useful.  (For instance, if the degree wrt to each variable, considered separately, is at most some small constant $c$, can we say something?  The last paragraph of my question handles the case $c=1$; can we say more?  Or, alternatively, if the total degree of $f$ is not too large, can we say something?)  

---

## 1 answers

### Answer by username_3 on 2015-12-22. Score: 10

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:

1. If $f$ is an elementary symmetric polynomial over a finite field then it can be computed by polynomial-size uniform $TC^0$ circuits.
2. 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.)
3. 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...


---

