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 polynomialsize linear threshold circuits of depth two with
polynomially growing weights. Goldmann and Karpinski proved that LT_{1}
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(n^{4} log n), a significant improvement
on the general bound of O(n^{12} log^{11}n) by
Hofmeister. 
View
Paper (PDF) 
