Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > AKIRA MARUOKA:
All reports by Author Akira Maruoka:

TR04-090 | 3rd November 2004
Kazuyuki Amano, Akira Maruoka

Better Simulation of Exponential Threshold Weights by Polynomial Weights

We give an explicit construction of depth two threshold circuit with polynomial weights and \tilde{O}(n^5) gates that computes an arbitrary threshold function. We also give the construction of such circuits with O(n^3/\log n) gates computing the COMPARISON and CARRY functions, and that with O(n^4/\log n) gates computing the ADDITION function. ... more >>>




ISSN 1433-8092 | Imprint