On Optimal Depth Threshold Circuits for Multiplication and Related Problems
Kai-Yeung Sunny Siu, Vwani Roychowdhury · SIAM Journal on Discrete Mathematics · 1994
Let $\widehat{LT}_d $ denote the class of functions that can be computed by depth-d threshold circuits with polynomial size and polynomially bounded integer weights. Using the results in [M. Goldman, J. Håstad, and A. Razborov, in Proc. 7th Annual Conference on Structure in Complexity Theory], [M. Goldman and M. Karpinski, Constructing depth$d+1$majority circuits that simulate depth d threshold circuits, unpublished] we show that multiple sum is in $\widehat{LT}_2 $, and multiplication and division are in $\widehat{LT}_3 $. Moreover, it follows from the lower-bound results in [A. Hajnal et al., IEEE Sympos. Foundations of Comput. Sci., 28 (1987), pp. 99–110], [T. Hofmeister and P. Pudlák, Forschungbericht Nr. 477 Uni Dortmund, 1992] that these threshold circuits are optimal in circuit depth. The authors also indicate that these techniques can be applied to construct polynomial-size depth-3 threshold circuits for powering and depth-4 threshold circuits for multiple product.