Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUB-POLYNOMIAL ALGORITHM:
Reports tagged with sub-polynomial algorithm:
TR02-052 | 3rd September 2002
Vince Grolmusz

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

Revisions: 1

Elementary symmetric polynomials $S_n^k$ are used as a
benchmark for the bounded-depth arithmetic circuit model of computation.
In this work we prove that $S_n^k$ modulo composite numbers $m=p_1p_2$
can be computed with much fewer multiplications than over any field, if
the coefficients of monomials $x_{i_1}x_{i_2}\cdots x_{i_k}$ ... more >>>




ISSN 1433-8092 | Imprint