TY - GEN

T1 - Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem

AU - Hellerstein, Lisa

AU - Kletenik, Devorah

AU - Liu, Naifeng

AU - Witter, R. Teal

N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85142753216&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85142753216&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-18367-6_10

DO - 10.1007/978-3-031-18367-6_10

M3 - Conference contribution

AN - SCOPUS:85142753216

SN - 9783031183669

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 190

EP - 210

BT - Approximation and Online Algorithms - 20th International Workshop, WAOA 2022, Proceedings

A2 - Chalermsook, Parinya

A2 - Laekhanukit, Bundit

PB - Springer Science and Business Media Deutschland GmbH

T2 - 20th International Workshop on Approximation and Online Algorithms, WAOA 2022

Y2 - 8 September 2022 through 9 September 2022

ER -