On another Boolean matrix

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 Ω(n 3/2) two-input gates in any monotone Boolean network computing them. In this note we show how this can be extended to Ω(n 5/3) two-input gates.

Authors

• Nicholas Pippenger

Keywords

No keywords are indexed for this paper.