9 by Springer-Verlag 1979 Some Remarks on Boolean Sums*

Summary. Neciporuk, Lamagna/Savage and Tarjan determined the mo-notone network complexity of a set of Boolean sums if any two sums have at most one variable in common. Wegener then solved the case that any two sums have at most k variables in common. We extend his methods and results and consider the case that any set of h + 1 distinct sums have at most k variables in common. We use our general results to explicitly construct a set of n Boolean sums over n variables whose monotone complexity is of order n 5/a. The best previously known bound was of order n 3/2. Related results were obtained independently by Pippenger. 1. Introduction, Notation