Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications

Elementary symmetric polynomials S n are used as a benchmark for the boundeddepth arithmetic circuit model of computation. In this work we prove that S n modulo composite numbers m = p 1 p 2 can be computed with much fewer multiplications than over any field, if the coefficients of monomials x i 1 x i 2 \Delta \Delta \Delta x i k are allowed to be 1 either mod p 1 or mod p 2 but not necessarily both. More exactly, we prove that for any constant k such a representation of S n can be computed modulo p 1 p 2 using only exp(O( log n log log n)) multiplications on the most restricted depth-3 arithmetic circuits, for min(p 1 ; p 2 ) ? k!