# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Some Remarks on Boolean Sums

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Mehlhorn, K. (1979). Some Remarks on Boolean Sums.* Acta Informatica,*
*12*, 371-375.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AF87-1

##### Abstract

Summary Neciporuk, Lamagna/Savage and Tarjan determined the monotone 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/3. The best previously
known bound was of order n 3/2. Related results were obtained independently by
Pippenger.
This paper was presented at the MFCS 79 Symposium, Olomouc, Sept. 79