A Note on Realizing Iterated Multiplication by Small Depth Threshold Circuits
Matthias Krause · MADOC (University of Mannheim) · 1995
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 approximation schemes over the set of all threshold functions. We use a lower bound argument based on probabilistic communication complexity.