Raymond F. Boyce, Donald D. Chamberlin, et al.
CACM
Paper
On another Boolean matrix
Abstract
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.
Related
Beomseok Nam, Henrique Andrade, et al.
ACM/IEEE SC 2006
Conference paper
Social networks and discovery in the enterprise (SaND)
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Kaoutar El Maghraoui, Gokul Kandiraju, et al.
WOSP/SIPEW 2010