Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem

Lisa Hellerstein, Devorah Kletenik, Naifeng Liu, R. Teal Witter

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We consider the Stochastic Boolean Function Evaluation (SBFE) problem where the task is to efficiently evaluate a known Boolean function f on an unknown bit string x of length n. We determine f(x) by sequentially testing the variables of x, each of which is associated with a cost of testing and an independent probability of being true. If a strategy for solving the problem is adaptive in the sense that its next test can depend on the outcomes of previous tests, it has lower expected cost but may take up to exponential space to store. In contrast, a non-adaptive strategy may have higher expected cost but can be stored in linear space and benefit from parallel resources. The adaptivity gap, the ratio between the expected cost of the optimal non-adaptive and adaptive strategies, is a measure of the benefit of adaptivity. We present lower bounds on the adaptivity gap for the SBFE problem for popular classes of Boolean functions, including read-once DNF formulas, read-once formulas, and general DNFs. Our bounds range from Ω(log n) to Ω(n/ log n), contrasting with recent O(1) gaps shown for symmetric functions and linear threshold functions.

    Original languageEnglish (US)
    Title of host publicationApproximation and Online Algorithms - 20th International Workshop, WAOA 2022, Proceedings
    EditorsParinya Chalermsook, Bundit Laekhanukit
    PublisherSpringer Science and Business Media Deutschland GmbH
    Number of pages21
    ISBN (Print)9783031183669
    StatePublished - 2022
    Event20th International Workshop on Approximation and Online Algorithms, WAOA 2022 - Potsdam, Germany
    Duration: Sep 8 2022Sep 9 2022

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume13538 LNCS
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Conference20th International Workshop on Approximation and Online Algorithms, WAOA 2022

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem'. Together they form a unique fingerprint.

    Cite this