  Recently, Deshpande et al. introduced a new measure of the complexity of a
Boolean function. We call this measure the "goal value" of the function. The
goal value of $f$ is defined in terms of a monotone, submodular utility
function associated with $f$. As shown by Deshpande et al., proving that a
Boolean function $f$ has small goal value can lead to a good approximation
algorithm for the Stochastic Boolean Function Evaluation problem for $f$. Also,
if $f$ has small goal value, it indicates a close relationship between two
other measures of the complexity of $f$, its average-case decision tree
complexity and its average-case certificate complexity. In this paper, we
explore the goal value measure in detail. We present bounds on the goal values
of arbitrary and specific Boolean functions, and present results on properties
of the measure. We compare the goal value measure to other, previously studied,
measures of the complexity of Boolean functions. Finally, we discuss a number
of open questions provoked by our work.
