On the goal value of a Boolean function

In recent work, Deshpande et al. introduced a new measure of the complexity of a Boolean function (Deshpande, Hellerstein, and Kletenik 2014). The measure is related to the maximum utility value of a certain monotone, submodular utility function associated with the Boolean function. We call this measure the “goal value” of the function. Proving that a Boolean function has small goal value can yield new bounds on the average-depth decision tree complexity of the function, and new approximation algorithms for its sequential testing problem. We present bounds on the goal values of arbitrary and specific Boolean functions. We also compare the goal value measure to other, previously studied, measures of the complexity of Boolean functions.