Complexity of information networks of depth 2 / D. Yu. Cherukhin. //Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika. 2009. № 1. P. 16-19
[Moscow Univ. Math. Bulletin. Vol. 64,
N 1, 2009. P. 16-19].
The lower bound \Omega(n\log_2 n) for the complexity of an arbitrary depth-two information network with n inputs and n outputs is proved providing the inputs are independent, the outputs are independent, and the total information of any input and any output is n times less than the entropy of any input or output. A similar estimate for Boolean depth-two circuits of functional elements is obtained as a corollary.
