On the Rational Degree of Boolean Functions and Applications.
Vishnu IyerSiddhartha JainMatt Kovacs-DeakVinayak M. KumarLuke SchaefferDaochen WangMichael WhitmeyerPublished in: Electron. Colloquium Comput. Complex. (2023)
Keyphrases
- boolean functions
- uniform distribution
- randomly generated
- relevant variables
- dnf formulae
- prime implicants
- pseudo boolean functions
- functional properties
- disjunctive normal form
- linear threshold
- threshold functions
- multi valued
- decision trees
- polynomial size
- binary decision diagrams
- membership queries
- bi decomposition
- read once formulas
- dnf formulas
- model checking
- genetic programming
- association rules