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.
Additional information:
Online-Ressource
Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation.
Search Authors in