One-way communication complexity of symmetric Boolean functions.
Jan ArpeAndreas JakobyMaciej LiskiewiczPublished in: RAIRO Theor. Informatics Appl. (2005)
Keyphrases
- boolean functions
- uniform distribution
- dnf formulae
- threshold functions
- relevant variables
- computational complexity
- read once formulas
- prime implicants
- polynomial size
- bounded treewidth
- multi valued
- membership queries
- binary decision diagrams
- linear threshold
- decision problems
- agnostic learning
- functional properties
- rough sets
- lower bound
- machine learning