Rectifier circuits of bounded depth

Abstract

Asymptotically tight bounds are obtained for the complexity of computation of the classes of (m,n)(m,n)-matrices with entries from the set 0,1,…,q−10,1,…,q−1 by rectifier circuits of bounded depth d,d, under some relations between mm, nn, and qq. In the most important case of q=2q=2, it is shown that the asymptotics of the complexity of Boolean (m,n)(m,n)-matrices, log n=o(m)n=o(m), log m=o(n)m=o(n), is achieved for the circuits of depth 3.
Illustr. 1, bibliogr. 11.