TY - JOUR
T1 - Submodular goal value of Boolean functions
AU - Bach, Eric
AU - Dusart, Jérémie
AU - Hellerstein, Lisa
AU - Kletenik, Devorah
N1 - Funding Information:
L. Hellerstein was partially supported by NSF Award IIS-1217968 . E. Bach was partially supported by NSF Award CCF-1420750 . D. Kletenik was partially supported by a PSC-CUNY Award, jointly funded by The Professional Staff Congress and The City University of New York . We thank Michael Saks for his observation that goal value can be computed by an integer program, and György Turán for supplying the reference to Salomaa’s paper for Lemma 2.
Publisher Copyright:
© 2017 Elsevier B.V.
PY - 2018/3/31
Y1 - 2018/3/31
N2 - 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 suggested by our work.
AB - 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 suggested by our work.
KW - Boolean functions
KW - Read-once formulas
KW - Submodularity
UR - http://www.scopus.com/inward/record.url?scp=85036652784&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85036652784&partnerID=8YFLogxK
U2 - 10.1016/j.dam.2017.10.022
DO - 10.1016/j.dam.2017.10.022
M3 - Article
AN - SCOPUS:85036652784
VL - 238
SP - 1
EP - 13
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
SN - 0166-218X
ER -