Nondeterministic Communication Complexity of Random Boolean Functions (Extended Abstract).
Mozhgan PourmoradnasseriDirk Oliver TheisPublished in: TAMC (2017)
Keyphrases
- extended abstract
- boolean functions
- randomly generated
- uniform distribution
- polynomial size
- threshold functions
- dnf formulae
- prime implicants
- relevant variables
- decision problems
- statistical queries
- functional properties
- computational complexity
- linear functions
- bounded treewidth
- multi valued
- membership queries
- worst case