11
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ If you are interested in computation over $\mathbb{R}$ you may want to clarify the model of computation. $\endgroup$
    – Kaveh
    Commented Dec 21, 2015 at 21:59
  • 1
    $\begingroup$ @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$. $\endgroup$
    – D.W.
    Commented Dec 22, 2015 at 0:49
  • 1
    $\begingroup$ How is f specified? This is crucial to the complexity of evaluation. $\endgroup$
    – Thomas Steinke
    Commented Dec 22, 2015 at 2:11
  • 2
    $\begingroup$ @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? $\endgroup$
    – D.W.
    Commented Dec 22, 2015 at 2:17
  • 1
    $\begingroup$ @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?) $\endgroup$
    – D.W.
    Commented Dec 22, 2015 at 2:47

1 Answer 1

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.