__
TR95-009 | 2nd February 1995 00:00
__

#### A note on realizing iterated multiplication by small depth threshold circuits

**Abstract:**
It is shown that decomposition via Chinise Remainder does not

yield polynomial size depth 3 threshold circuits for iterated

multiplication of n-bit numbers. This result is achieved by

proving that, in contrast to multiplication of two n-bit

numbers, powering, division, and other related problems, the

resulting subproblems, iterated multiplication modulo

polylog(n)-bit numbers, do not have polynomial size approxi-

mation schemes over the set of all threshold functions.

We use a lower bound argument based on probabilistic

communication complexity.