One-Way Communication Complexity of Symmetric Boolean Functions
Jan ArpeAndreas JakobyMaciej LiskiewiczPublished in: Electron. Colloquium Comput. Complex. (2003)
Keyphrases
- boolean functions
- uniform distribution
- threshold functions
- polynomial size
- computational complexity
- dnf formulae
- prime implicants
- machine learning
- decision problems
- bi decomposition
- binary decision diagrams
- bounded treewidth
- decision trees
- relevant variables
- linear threshold
- membership queries
- worst case
- multi valued
- rough sets