Optimal Bounds for the Approximation of Boolean Functions and Some Applications.
Alexander E. AndreevAndrea E. F. ClementiJosé D. P. RolimPublished in: Theor. Comput. Sci. (1997)
Keyphrases
- boolean functions
- linear functions
- error tolerance
- uniform distribution
- linear threshold
- worst case
- error bounds
- constant factor
- dnf formulae
- threshold functions
- membership queries
- upper bound
- prime implicants
- lower bound
- optimal solution
- functional properties
- approximation algorithms
- upper and lower bounds
- relevant variables
- binary decision diagrams
- approximation guarantees
- read once formulas
- arbitrarily close