On the Combinational Complexity of Certain Symmetric Boolean Functions.

Larry J. Stockmeyer

Published in: Math. Syst. Theory (1977)

Keyphrases

boolean functions
uniform distribution
threshold functions
polynomial size
relevant variables
prime implicants
computational complexity
membership queries
dnf formulae
bounded treewidth
pseudo boolean functions
worst case
multi valued
linear threshold
functional properties
disjunctive normal form