A Comparison of the Computational Power of Sigmoid and Boolean Threshold Circuits

We examine the power of constant depth circuits with sigmoid (i.e. smooth) threshold gates for computing boolean functions. It is shown that, for depth 2, constant size circuits of this type are strictly more powerful than constant size boolean threshold circuits (i.e. circuits with linear threshold gates). On the other hand it turns out that, for any constant depth d, polynomial size sigmoid threshold circuits with polynomially bounded weights compute exactly the same boolean functions as the corresponding circuits with linear threshold gates. Partially supported by NSF-CCR-8805978 and AFOSR-87-0400 y Partially supported by Siemens Corporate Research and AFOSR-88-0235 and AFOSR-91-0343 1 Introduction Research on neural networks has led to the investigation of massively parallel computational models that consist of analog computational elements. Usually these analog computational elements are assumed to be smooth threshold gates, i.e.fl-gates for some nondecreasing differentiabl..