Trading Weight Size for Circuit Depth: A Circuit for Comparison
Vasken Bohossian, Marc D. Riedel, Jehoshua Bruck · CaltechAUTHORS (California Institute of Technology) · 1998
NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract included in .pdf document. We present an explicit construction of a circuit for the COMPARISON function in [...], the class of polynomial-size linear threshold circuits of depth two with polynomially growing weights. Goldmann and Karpinski proved that [...] in [4]. Hofmeister presented a simplified version of the same result in [6]. We have further simplified the results of these two papers by limiting ourselves to the simulation of COMPARISON. Our construction has size [...], a significant improvement on the general bound of [...] in [6].