Publication
Theoretical Computer Science
Paper

An explicit construction of short monotone formulae for the monotone symmetric functions

View publication

Abstract

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 O(nlogn) k 2log*n occurences of variables. © 1978.

Date

Publication

Theoretical Computer Science

Authors

Topics

Share