TY - JOUR

T1 - The Stochastic Boolean Function Evaluation problem for symmetric Boolean functions

AU - Gkenosis, Dimitrios

AU - Grammel, Nathaniel

AU - Hellerstein, Lisa

AU - Kletenik, Devorah

N1 - Funding Information:
Partial support for this work came from National Science Foundation, United States Award IIS-1217968 (for all authors), from National Science Foundation Award IIS-1909335 (for L. Hellerstein), and from a PSC-CUNY Award jointly funded by The Professional Staff Congress, United States and The City University of New York, United States (for D. Kletenik).
Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2022/3/15

Y1 - 2022/3/15

N2 - We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an O(logn)-approximation algorithm, based on the submodular goal-value approach of Deshpande, Hellerstein and Kletenik. Our second algorithm, which is simple, is based on the algorithm solving the SBFE problem for k-of-n functions, due to Salloum, Breuer, and Ben-Dov. It achieves a (B−1) approximation factor, where B is the number of blocks of 0’s and 1’s in the standard vector representation of the symmetric Boolean function. As part of the design of the first algorithm, we prove that the goal value of any symmetric Boolean function is less than n(n+1)/2. Finally, we give an example showing that for symmetric Boolean functions, minimum expected verification cost and minimum expected evaluation cost are not necessarily equal. This contrasts with a previous result, given by Das, Jafarpour, Orlitsky, Pan and Suresh, which showed that equality holds in the unit-cost case.

AB - We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an O(logn)-approximation algorithm, based on the submodular goal-value approach of Deshpande, Hellerstein and Kletenik. Our second algorithm, which is simple, is based on the algorithm solving the SBFE problem for k-of-n functions, due to Salloum, Breuer, and Ben-Dov. It achieves a (B−1) approximation factor, where B is the number of blocks of 0’s and 1’s in the standard vector representation of the symmetric Boolean function. As part of the design of the first algorithm, we prove that the goal value of any symmetric Boolean function is less than n(n+1)/2. Finally, we give an example showing that for symmetric Boolean functions, minimum expected verification cost and minimum expected evaluation cost are not necessarily equal. This contrasts with a previous result, given by Das, Jafarpour, Orlitsky, Pan and Suresh, which showed that equality holds in the unit-cost case.

KW - Approximation algorithms

KW - Boolean functions

KW - Sequential testing

KW - Submodularity

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

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

U2 - 10.1016/j.dam.2021.12.001

DO - 10.1016/j.dam.2021.12.001

M3 - Article

AN - SCOPUS:85121922966

VL - 309

SP - 269

EP - 277

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -