Polynomial-Time Recognition of 2-Monotonic Positive Boolean Functions Given by an Oracle.
Endre BorosPeter L. HammerToshihide IbarakiKazuhiko KawakamiPublished in: SIAM J. Comput. (1997)
Keyphrases
- boolean functions
- statistical queries
- dnf formulae
- read once formulas
- uniform distribution
- polynomial size
- truth table
- dnf formulas
- disjunctive normal form
- membership queries
- threshold functions
- monotone boolean functions
- prime implicants
- positive and negative
- relevant variables
- bounded treewidth
- multi valued
- functional properties
- linear threshold
- monotonicity constraints
- binary decision diagrams
- target concept
- pac learning
- special case