A New Lower Bound for the Number of Switches in Rearrangeable Networks
Nicholas J. Pippenger · SIAM Journal on Algebraic and Discrete Methods · 1980
For the commonest model of rearrangeable networks with n inputs and n outputs, it is shown that such a network must contain at least $6n \log _6 n + O( n )$ switches. Similar lower bounds for other models are also presented.