<p>One challenge is that if you remove the "monotone" restriction, we <em>do</em> 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.</p>

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

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

<p>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)$.</p>

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

<p>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$).</p>

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

CC BY-SA 3.0
2016-01-05T11:44:51.630Z
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.
Stasys
CC BY-SA 3.0
2016-01-05T18:18:40.070Z
@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...
Joshua Grochow
CC BY-SA 3.0
2016-01-05T19:08:26.723Z
@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.
Stasys
CC BY-SA 3.0
2016-01-05T05:28:17.783Z
2016-01-05T05:28:17.783Z
D.W.
<p>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.</p>

<blockquote>
<b> Question:</b>
Is a lower bound of $\Omega(kn)$  known?
</blockquote>

<p>A $(+,\times)$ circuit is <i>skew</i> 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 <b>exactly</b> $k(n-k+1)$ product gates. The <i>upper</i> bound follows from Fig. 1:
<a href="https://i.sstatic.net/SNBOw.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/SNBOw.png" alt="enter image description here"></a>
<p>
 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>
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 <a href="http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/" rel="nofollow noreferrer">Ingo Wegener's book</a>. The <a href="https://en.wikipedia.org/wiki/Sorting_network" rel="nofollow noreferrer">AKS sorting network</a> also implies that $O(n\log n)$ gates are sufficient in this (boolean) case. Actually, <a href="http://www.sciencedirect.com/science/article/pii/030439758390110X" rel="nofollow noreferrer">Baur and Strassen</a> have proved a tight bound $\Theta(n\log n)$ on the size of <i>non-monotone</i> arithmetic circuit for $S_{n/2}^n$. But what about <i>monotone</i> arithmetic circuits?</p>

<cc.complexity-theory><circuit-complexity><lower-bounds><arithmetic-circuits><dynamic-programming>
Monotone arithmetic circuit complexity of elementary symmetric polynomials?
Stasys
# Monotone arithmetic circuit complexity of elementary symmetric polynomials?

(Asked by: username_0 on 2016-01-04)

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](https://i.sstatic.net/SNBOw.png)](https://i.sstatic.net/SNBOw.png)

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](http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/). The [AKS sorting network](https://en.wikipedia.org/wiki/Sorting_network) also implies that $O(n\log n)$ gates are sufficient in this (boolean) case. Actually, [Baur and Strassen](http://www.sciencedirect.com/science/article/pii/030439758390110X) 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?

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, arithmetic-circuits, dynamic-programming


---

## 1 answers

### Answer by username_1 on 2016-01-05. Score: 6

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.

> **Comments:**
> **username_0**: username_1, 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.  
> **username_2**: @username_0: 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...  
> **username_0**: @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.  

---

