Ronald Fagin, Jurg Nievergelt, et al.
ACM Transactions on Database Systems (TODS)
We study the realization of monotone Boolean functions by networks. Our main result is a precise version of the following statement: the complexity of realizing a monotone Boolean function of n arguments is less by the factor (2/πn)1/2, where π is the circular ratio, than the complexity of realizing an arbitrary Boolean function of n arguments. The proof combines known results concerning monotone Boolean functions with new methods relating the computing abilities of networks and machines. © 1978 Springer-Verlag New York Inc.
Ronald Fagin, Jurg Nievergelt, et al.
ACM Transactions on Database Systems (TODS)
Nicholas Pippenger
IEEE Transactions on Communications
Nicholas Pippenger
Theoretical Computer Science
Maria Klawe, Wolfgang J. Paul, et al.
STOC 1984