Approximate evaluations of characteristic polynomials of Boolean functions (Q5958111)

The paper studies the approximations of the values of characteristic polynomials of Boolean functions. As a result of arithmetization of Boolean functions, characteristic polynomials are multlinear extensions of Boolean functions. They are conceived as potential tools for circuit testing purposes. In this paper the approximations are used for the ``black-box'' case, i.e. the internal structure of the tested circuit is not known, but it is only possible to supply inputs and observe outputs. By a characteristic polynomial of the given Boolean function we mean the real-valued polynomial reduced to the \([0,1]^n\) cube obtained from the standard sum of products of \(f\), where the Boolean variables are substituted by real variables, negation of the variable \(x\) by \((1-x)\), AND by product, and OR by summation. The idea of this paper is to approximate the real values of characteristic polynomials using the binary evaluations of the corresponding Boolean functions. The errors, being the result of approximation, are defined in the worst case, average cases and randomized setting. It is shown that the value of a characteristic polynomial is given by a multivariate integral over the unit cube \([0,1]^n\). Thus the Monte Carlo algorithms may be used for the approximate evaluation of a characteristic polynomial in the randomized setting. Let \(k\) be the number of known values of the \(n\)-variable Boolean function. Suppose that with \(k\) Boolean function evaluations the approximation error lower bound is \(e_k\). The relative error \(e_k/e_0\) is the reduction of errors with \(k\) Boolean function evaluations from the initial error without any Boolean values. Let \(k(n,\varepsilon)\) be the smallest number of \(n\) variable Boolean function values needed to obtain a relative error \(\varepsilon\). It is proved that \(k(n,\varepsilon)\) is exponential in \(n\) for each \(\varepsilon\) in the worst and average case settings, which means that the problem of approximate evaluations of characteristic polynomials in the assumed model is intractable. In the randomized settings \(k(n,\varepsilon)\) is polynomial in \(1/\varepsilon\) and the problem is tractable in \(1/\varepsilon\).