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 complexityof 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 productgate 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 minimalmonotone arithmetic skew circuit for $S_k^n$ has exactly $k(n-k+1)$ product gates. The upper bound follows from Fig. 1: 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?
Monotone arithmetic circuit complexity of elementary symmetric polynomials?
cc.complexity theory;circuit complexity;lower bounds;arithmetic circuits;dynamic programming