|
A note on realizing iterated multiplication by small depth threshold circuits
Krause, Matthias
|
URL:
|
https://eccc.weizmann.ac.il/report/1995/009/
|
|
Dokumenttyp:
|
Arbeitspapier
|
|
Erscheinungsjahr:
|
1995
|
|
Titel einer Zeitschrift oder einer Reihe:
|
Electronic Colloquium on Computational Complexity : ECCC
|
|
Band/Volume:
|
TR95-009
|
|
Ort der Veröffentlichung:
|
Trier
|
|
Verlag:
|
Universität Trier
|
|
ISSN:
|
1433-8092
|
|
Sprache der Veröffentlichung:
|
Englisch
|
|
Einrichtung:
|
Fakultät für Wirtschaftsinformatik und Wirtschaftsmathematik > Theoretische Informatik (Krause 1996-)
|
|
Fachgebiet:
|
004 Informatik
|
|
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.
|
|
Zusätzliche Informationen:
|
Online-Ressource
|
 | Dieser Datensatz wurde nicht während einer Tätigkeit an der Universität Mannheim veröffentlicht, dies ist eine Externe Publikation. |
 Suche Autoren in
Sie haben einen Fehler gefunden? Teilen Sie uns Ihren Korrekturwunsch bitte hier mit: E-Mail
Actions (login required)
 |
Eintrag anzeigen |
|
|
