ECCC-Report TR04-090https://eccc.weizmann.ac.il/report/2004/090Comments and Revisions published for TR04-090en-usWed, 03 Nov 2004 20:31:10 +0200
Paper TR04-090
| Better Simulation of Exponential Threshold Weights by Polynomial Weights |
Kazuyuki Amano,
Akira Maruoka
https://eccc.weizmann.ac.il/report/2004/090We 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.
Wed, 03 Nov 2004 20:31:10 +0200https://eccc.weizmann.ac.il/report/2004/090