Abstract
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.
Original language | English (US) |
---|---|
State | Published - Jan 1 2016 |
Event | 2016 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 - Fort Lauderdale, United States Duration: Jan 4 2016 → Jan 6 2016 |
Conference
Conference | 2016 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 |
---|---|
Country/Territory | United States |
City | Fort Lauderdale |
Period | 1/4/16 → 1/6/16 |
ASJC Scopus subject areas
- Applied Mathematics
- Artificial Intelligence