Approximate Evaluations of Characteristic Polynomials of Boolean Functions

Motivated by combinational circuit verification and testing, we study the approximate evaluation of characteristic polynomials of Boolean functions. We consider an oracle model in which the values of the characteristic polynomials are approximated by the evaluations of the corresponding Boolean functions. The approximation error is defined in the worst case, average case and randomized settings. We derive the lower bounds on the approximation errors in terms of the number of Boolean function evaluations. We design algorithms with an error that matches the lower bound. Let k(epsilon, eta) denote the minimal number of Boolean function evaluations needed to reduce the initial error by a factor of epsilon where eta is the number of Boolean variables. We show that k (epsilon, eta) is exponential in eta in the worst case and average case settings, and is independent of eta and of other epsilon sup (-2) in the randomized setting.