Computing Elementary Symmetric Polynomials with a Sublinear Number of Multiplications

Original · EN

Elementary symmetric polynomials Sₙᵏ are used as a benchmark for the bounded-depth arithmetic circuit model of computation. In this work we prove that Sₙᵏ modulo composite numbers m=p₁p₂ can be computed with much fewer multiplications than over any field, if the coefficients of monomials xᵢ₁xᵢ₂... xᵢₖ are allowed to be 1 either mod p₁ or mod p₂ but not necessarily both. More exactly, we prove that for any constant k such a representation of Sₙᵏ can be computed modulo p₁p₂ using only (O(√ n n)) multiplications on the most restricted depth-3 arithmetic circuits, for (p₁,p₂)>k!. Moreover, the number of multiplications remain sublinear while k=O(n). In contrast, the well-known Graham-Pollack bound yields an n-1 lower bound for the number of multiplications even for the exact computation (not the representation) of Sₙ². Our results generalize for other non-prime power composite moduli as well. The proof uses the famous BBR-polynomial of Barrington, Beigel and Rudich.