Trading Weight Size for Circuit Depth: An \widehat{LT}2 Circuit for Comparison
Vasken Bohossian, Marc D. Riedel,  and Jehoshua Bruck

Abstract

We present an explicit construction of a circuit for the COMPARISON function in \widehat{LT}2, the class of polynomial-size linear threshold circuits of depth two with polynomially growing weights. Goldmann and Karpinski proved that LT1 is contained in \widehat{LT}2 in 1993. Hofmeister presented a simplified version of the same result in 1996. We have further simplified the results of these two papers by limiting ourselves to the simulation of COMPARISON. Our construction has size O(n4 log n), a significant improvement on the general bound of O(n12 log11n) by Hofmeister.


View Paper (PDF)