Optimal Bounds on the Approximation of Boolean Functions with Consequences on the Concept of Hardware.
Alexander E. AndreevAndrea E. F. ClementiJosé D. P. RolimPublished in: STACS (1996)
Keyphrases
- boolean functions
- error tolerance
- linear threshold
- worst case
- linear functions
- uniform distribution
- error bounds
- membership queries
- constant factor
- functional properties
- dnf formulae
- relevant variables
- target concept
- multi valued
- upper bound
- optimal solution
- approximation algorithms
- low cost
- disjunctive normal form
- lower bound
- binary decision diagrams
- dnf formulas
- upper and lower bounds
- threshold functions