2002/07/03 by Vince Grolmusz, Grolmusz, Vince
Computer Science · #Coding theory and cryptography #Numerical Methods and Algorithms #Polynomial and algebraic computation #cs.CC #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0207009
10 pages
arxiv created 2002/07/03 · arxiv updated 2009/11/30
Elementary symmetric polynomials Snk are used as a benchmark for the bounded-depth arithmetic circuit model of computation. In this work we prove that Snk modulo composite numbers m=p1p2 can be computed with much fewer multiplications than over any field, if the coefficients of monomials xi1xi2... xik are allowed to be 1 either mod p1 or mod p2 but not necessarily both. More exactly, we prove that for any constant k such a representation of Snk can be computed modulo p1p2 using only exp(O(√(log n)loglog n)) multiplications on the most restricted depth-3 arithmetic circuits, for min(p1,p2)>k!. Moreover, the number of multiplications remain sublinear while k=O(loglog 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 Sn2. Our results generalize for other non-prime power composite moduli as well. The proof uses the famous BBR-polynomial of Barrington, Beigel and Rudich.