Approximate evaluations of characteristic polynomials of Boolean functions

Motivated by combinational circuit verification and testing, we study the a pproximate evaluation of characteristic polynomials of Boolean functions. W e consider an oracle model in which the values of the characteristic polyno mials are approximated using the evaluations of the corresponding Boolean f unctions. The approximation error is defined in the worst case, average cas e and randomized settings. We derive lower bounds on the approximation erro rs in terms of the number of Boolean function evaluations. We design algori thms with an error that matches the lower bound. Let k(epsilon, n) denote t he minimal number of Boolean function evaluations needed to reduce the init ial error by a factor of E where n is the number of Boolean variables. We s how that k(epsilon ,n) is exponential in n in the worst and average case se ttings, and that it is independent of n and of order epsilon (-2) in the ra ndomized setting. (C) 2001 Elsevier Science B,V. All rights reserved.