ECCC
Electronic Colloquium on Computational Complexity
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}$ are allowed to be ... more >>>



ISSN 1433-8092 | Imprint