The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables. I am interested in the monotone arithmetic $(+,\times)$ circuit complexity of this polynomial. A simple dynamic programming algorithm (as well as Fig. 1 below) gives a $(+,\times)$ circuit with $O(kn)$ gates.

Question: Is a lower bound of $\Omega(kn)$ known?

A $(+,\times)$ circuit is skew if at least one of the two inputs of each product gate is a variable. Such a circuit is actually the same as switching-and-rectifying network (a directed acyclic graph with some edges labeled by variables; each s-t path gives the product of its labels, and the output is the sum of over all s-t paths). Already 40 years ago, Markov proved a surprisingly tight result: a minimal monotone arithmetic skew circuit for $S_k^n$ has exactly $k(n-k+1)$ product gates. The upper bound follows from Fig. 1: enter image description here

But I haven't seen any attempt to prove such a lower bound for non-skew circuits. Is this just our "arrogance", or are there some inherent difficulties observed along the way?

P.S. I know that $\Omega(n\log n)$ gates are necessary to simultaneously compute all $S_1^n,\ldots,S_n^n$. This follows from the lower bound on the size of monotone boolean circuits sorting the 0-1 input; see page 158 of Ingo Wegener's book. The AKS sorting network also implies that $O(n\log n)$ gates are sufficient in this (boolean) case. Actually, Baur and Strassen have proved a tight bound $\Theta(n\log n)$ on the size of non-monotone arithmetic circuit for $S_{n/2}^n$. But what about monotone arithmetic circuits?


1 Answer 1


One challenge is that if you remove the "monotone" restriction, we do know how to compute such things efficiently. You can compute the value of all $S_0^n,\dots,S_n^n$ (evaluate all $n+1$ elementary symmetric polynomials) in $O(n \log^2 n)$ time, using FFT-based polynomial multiplication. So, proving a $\Omega(nk)$ lower bound in the monotone circuit model would require proving a $\Omega(n^2)$ lower bound on polynomial multiplication.

Here's how. Introduce a formal unknown $y$, and consider the polynomial

$$P(y) = \prod_{i=1}^n (1 + x_i y).$$

Note that since the $x_i$'s are known constants, this is a univariate polynomial with unknown $y$ and with degree $n$. Now you can note that the coefficient of $y^k$ in $P(y)$ is exactly $S_k^n$, so to evaluate all the $S_0^n,\dots,S_n^n$, it suffices to compute $P(y)$.

This makes it possible to compute $P(y)$ in $O(n \lg^2 n)$ time: build a balanced binary tree of polynomials with the $(1+x_i y)$'s at the leaves, and multiply the polynomials. Multiplying two polynomials of degree $d$ takes $O(d \lg d)$ time using FFT techniques, so we get the recurrence $T(n) = 2 T(n/2) + O(n \lg n)$, which solves to $T(n) = O(n \lg^2 n)$. For convenience, I am ignoring $\text{poly}(\lg \lg n)$ factors.

If you care about the case where $k$ is very small, you can compute $S_0^n,\dots,S_k^n$ in $O(n \lg^2 k)$ time using similar tricks, keeping in mind that you only care about $P(x) \bmod y^{k+1}$ (i.e., throwing away all terms of $y^{k+1}$ or higher powers of $y$).

Of course, the FFT uses subtraction, so naively it's not expressible in a monotone circuit. I don't know whether there's some other way to multiply polynomials efficiently with monotone arithmetic circuits, but any efficient monotone method for polynomial multiplication immediately leads to an algorithm for your problem as well. So, lower bounds on your problem require/imply lower bounds for polynomial multiplication.

  • 2
    $\begingroup$ D.W., thanks for recalling this construction! It is usually attributed to Ben-Or, and I should have mentioned it. The construction also gives a <i>formula</i> of size $O(n^2)$ and depth only $3$ (!) computing the operator $S_0^n,\ldots,S_n^n$ (by evaluating $P(y)$ at some $n+1$ points). This was used to separate homogeneous and non-homogeneous small-depth formulas. But, as you mention, the construction substantially uses subtraction. So, my question asks: how "substantial" this use actually is? This could be interesting also in restricted-depth scenario. $\endgroup$
    – Stasys
    Jan 5, 2016 at 11:44
  • 3
    $\begingroup$ @Stasys: I think subtraction is pretty crucial. Viz. the Nisan-Wigderson lower bound on depth 3 homogeneous circuits; in homogeneous depth 3 circuits, the point is that it's useless to compute terms whose degrees differ from the degree of the output. So this limits the kinds of cancellations that can happen. Whereas in the Ben-Or construction, to compute $S_k^n$, one needs to compute a polynomial of degree $n$ (even though the output has degree $k < n$), and then crucially use cancellation to get rid of the terms of degrees $> k$. This isn't a proof, just some intuition... $\endgroup$ Jan 5, 2016 at 18:18
  • $\begingroup$ @Joshua: yes, we know that the coefficients of the variable $y$ in the polynomial $P(y,x)$ are exactly the polynomials $S_k^n(x)$. But we need Gauss (and so - subtractions) to extract these coefficients from $n+1$ values of $P(y)$ on $n+1$ distinct points. My question asks whether the "monotone word" has no Gauss indeed, in this case. (With a guessed answer - NO.) I am not sure that for this, it is enough to get rid of terms of degrees $> k$. We have to find these $k$ first coefficients. $\endgroup$
    – Stasys
    Jan 5, 2016 at 19:08

Your Answer

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