Rectifier Circuits of Bounded Depth

Abstract

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