Computing Elementary Symmetric Polynomials with a Subpolynomial Numberof Multiplications
Vince I. Grolmusz · SIAM Journal on Computing · 2003
Elementary symmetric polynomials $S_n^k$ are the building blocks of symmetric polynomials. In this work we prove that for constant k's, $S_n^k$ modulo composite numbers m=p 1 p 2 can be computed using only n o (1) multiplications if the coefficients of monomials x i 1 x i 2 . . . x i k are allowed to be 1 either mod p 1 or mod p 2 but not necessarily both. To the best of our knowledge, no previous result yielded even a sublinear (i.e., $n^{\varepsilon}$, $0 < \varepsilon < 1$) number of multiplications for similar tasks. Moreover, our algorithm fits in the model of the most restrictive depth-3 arithmetic circuits (homogeneous, multilinear, or the graph model). In contrast, by a lower bound of Nisan and Wigderson [Comput. Complexity, 6 (1997), pp. 217--234], any homogeneous depth-3 circuit needs size $\Omega((n/2k)^{k/2})$ for computing $S_n^k$ modulo primes. Moreover, the number of multiplications in our algorithm remains sublinear while k=O(log log n). Our results generalize for other nonprime-power composite moduli as well. The proof uses perfect hashing functions and the famous BBR polynomial of Barrington, Beigel, and Rudich.