On the Complexity of Balanced Boolean Functions.

Anna Bernasconi

Published in: Inf. Process. Lett. (1999)

Keyphrases

boolean functions
uniform distribution
polynomial size
worst case
prime implicants
dnf formulae
threshold functions
relevant variables
lower bound
linear threshold
bounded treewidth
dnf formulas
functional properties
bi decomposition
pseudo boolean functions
linear functions
multi valued