Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR95-009 | 2nd February 1995 00:00

A note on realizing iterated multiplication by small depth threshold circuits

RSS-Feed




TR95-009
Authors: Matthias Krause
Publication: 3rd February 1995 20:54
Downloads: 1479
Keywords: 


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.



ISSN 1433-8092 | Imprint