Approximation Algorithms for Stochastic Boolean Function Evaluation and Stochastic Submodular Set Cover

Amol Deshpande, Lisa Hellerstein, Devorah Kletenik

Stochastic Boolean Function Evaluation is the problem of determining the value of a given Boolean function f on an unknown input x, when each bit of x_i of x can only be determined…