Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR04-090 | 3rd November 2004 00:00

Better Simulation of Exponential Threshold Weights by Polynomial Weights

RSS-Feed




TR04-090
Authors: Kazuyuki Amano, Akira Maruoka
Publication: 3rd November 2004 20:31
Downloads: 1918
Keywords: 


Abstract:

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. These improve the previously known constructions on its size and simplicity.



ISSN 1433-8092 | Imprint