Better Simulation of Exponential Threshold Weights by Polynomial Weights

摘要

We give an explicit construction of depth two threshold circuit with polynomial weights and O(n~5) gates that computes an arbitrary threshold function. We also give the construction of such circuits with O(n~3) gates computing the COMPARISON and CARRY functions, and that with O(n~4) gates computing the ADDITION function. These improve the previously known constructions on its size and simplicity.