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.