One-Way Communication Complexity of Symmetric Boolean Functions.
Jan ArpeAndreas JakobyMaciej LiskiewiczPublished in: FCT (2003)
Keyphrases
- boolean functions
- uniform distribution
- polynomial size
- threshold functions
- relevant variables
- computational complexity
- dnf formulae
- membership queries
- prime implicants
- functional properties
- worst case
- bounded treewidth
- truth table
- linear functions
- linear threshold
- multi valued
- dnf formulas
- binary decision diagrams
- sample size