On the goal value of a Boolean function

Eric Bach, Lisa Hellerstein, Devorah Kletenik

    Research output: Contribution to conferencePaperpeer-review

    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 languageEnglish (US)
    StatePublished - Jan 1 2016
    Event2016 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016 - Fort Lauderdale, United States
    Duration: Jan 4 2016Jan 6 2016

    Conference

    Conference2016 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2016
    CountryUnited States
    CityFort Lauderdale
    Period1/4/161/6/16

    ASJC Scopus subject areas

    • Applied Mathematics
    • Artificial Intelligence

    Fingerprint Dive into the research topics of 'On the goal value of a Boolean function'. Together they form a unique fingerprint.

    Cite this