On the Power of Choice for Boolean Functions.
Nicolas FraimanLyuben LichevDieter MitschePublished in: SIAM J. Discret. Math. (2022)
Keyphrases
- boolean functions
- uniform distribution
- threshold functions
- power consumption
- dnf formulae
- prime implicants
- relevant variables
- membership queries
- binary decision diagrams
- functional properties
- read once formulas
- bi decomposition
- pseudo boolean functions
- truth table
- disjunctive normal form
- polynomial size
- dnf formulas
- multi valued
- learning theory