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.