A note on realizing iterated multiplication by small depth threshold circuits


Krause, Matthias



URL: https://eccc.weizmann.ac.il/report/1995/009/
Document Type: Working paper
Year of publication: 1995
The title of a journal, publication series: Electronic Colloquium on Computational Complexity : ECCC
Volume: TR95-009
Place of publication: Trier
Publishing house: Universität Trier
ISSN: 1433-8092
Publication language: English
Institution: School of Business Informatics and Mathematics > Theoretische Informatik (Krause 1996-)
Subject: 004 Computer science, internet
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 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.




Metadata export


Citation


+ Search Authors in

+ Page Views

Hits per month over past year

Detailed information



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item