The complexity of depth-two information networks
D. Yu. Cherukhin · Moscow University Mathematics Bulletin · 2009
The lower bound Ω(n log2 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.