On Another Boolean Matrix

Authors

Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1980

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 Ω(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.

Rights Information

© 1980 Elsevier Ltd.

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

DOI

10.1016/0304-3975(80)90034-1

Recommended Citation

Nicholas Pippenger, On another Boolean matrix, Theoretical Computer Science, Volume 11, Issue 1, May 1980, Pages 49-56, ISSN 0304-3975, 10.1016/0304-3975(80)90034-1. (http://www.sciencedirect.com/science/article/pii/0304397580900341)