| Links du Jour |
|
Symbool Citeseer ACM Portal IEEE Xplore DBLP Trier U.S. Patents Caltech Library |
|
Kevin's Pictures My Pictures |
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. |
