The complexity of AND - decomposition of Boolean functions.
Pavel G. EmelyanovDenis K. PonomaryovPublished in: Discret. Appl. Math. (2020)
Keyphrases
- boolean functions
- bi decomposition
- uniform distribution
- functional decomposition
- polynomial size
- relevant variables
- prime implicants
- threshold functions
- functional properties
- worst case
- multi valued
- linear threshold
- bounded treewidth
- membership queries
- dnf formulae
- disjunctive normal form
- decision rules
- read once formulas
- lower bound
- pseudo boolean functions