Qing Li, Zhigang Deng, et al.
IEEE T-MI
In his paper "On a Boolean matrix", Nechiporuk gave an explicit example of a set of n homogeneous monotone Boolean functions of the first degree in n variables that require Ω(n3/2) two-input gates in any monotone Boolean network computing them. In this note we show how this can be extended to Ω(n5/3) two-input gates. © 1980.
Qing Li, Zhigang Deng, et al.
IEEE T-MI
Eric Price, David P. Woodruff
FOCS 2011
Chi-Leung Wong, Zehra Sura, et al.
I-SPAN 2002
György E. Révész
Theoretical Computer Science