An Explicit Construction of Short Monotone Formulae for the Monotone Symmetric Functions
We construct formulae that assume the value 1 when and only when at least k of their n variables assume the value 1, using only conjunction and disconjunction, and having (for any fixed k) only [image of equation]* occurrences of variables.
*Image was removed for formatting purposes.
© 1978 Elsevier Ltd.
Mark Kleiman, Nicholas Pippenger, An explicit construction of short monotone formulae for the monotone symmetric functions, Theoretical Computer Science, Volume 7, Issue 3, December 1978, Pages 325-332, ISSN 0304-3975, 10.1016/0304-3975(78)90021-X. (http://www.sciencedirect.com/science/article/pii/030439757890021X)