The Complexity of Symmetric Boolean Functions.

Published in: Computation Theory and Logic (1987)

Keyphrases

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