ECCC-Report TR02-052https://eccc.weizmann.ac.il/report/2002/052Comments and Revisions published for TR02-052en-usMon, 11 Nov 2002 00:00:00 +0200
Revision 1
| Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications Revision of: TR02-052 |
Vince Grolmusz
https://eccc.weizmann.ac.il/report/2002/052#revision1Mon, 11 Nov 2002 00:00:00 +0200https://eccc.weizmann.ac.il/report/2002/052#revision1
Paper TR02-052
| Computing Elementary Symmetric Polynomials with a Sub-Polynomial Number of Multiplications |
Vince Grolmusz
https://eccc.weizmann.ac.il/report/2002/052Elementary 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 1 either mod $p_1$ or mod $p_2$ but not necessarily both. More
exactly, we prove that for any constant $k$ such a representation of
$S_n^k$ can be computed modulo $p_1p_2$ using only $\exp(O(\sqrt{\log
n}\log\log n))$ multiplications on the most restricted depth-3 arithmetic
circuits, for $\min({p_1,p_2})>k!$. Moreover, the number of
multiplications remain sublinear while $k=O(\log\log n).$
In contrast, the well-known Graham-Pollack bound yields an $n-1$ lower
bound for the number of multiplications even for the second elementary symmetric polynomial $S_n^2$.
Our results generalize for other non-prime power composite moduli as
well. The proof uses perfect hashing functions and the famous BBR-polynomial of Barrington, Beigel and
Rudich.
Mon, 16 Sep 2002 18:47:31 +0300https://eccc.weizmann.ac.il/report/2002/052