Approximation of Boolean Functions by Combinatorial Rectangles
Martin SauerhoffPublished in: Electron. Colloquium Comput. Complex. (2000)
Keyphrases
- boolean functions
- uniform distribution
- axis parallel
- linear functions
- dnf formulae
- membership queries
- relevant variables
- functional properties
- approximation algorithms
- threshold functions
- bi decomposition
- prime implicants
- linear threshold
- read once formulas
- polynomial size
- multi valued
- pseudo boolean functions
- disjunctive normal form
- dnf formulas
- upper bound