# The Stochastic Boolean Function Evaluation Problem for Symmetric Boolean Functions

arXiv: https://arxiv.org/abs/2111.08793 · HTML: https://mlsanity.com/paper/2111.08793/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Nov 2021.

## Built on by (most cited first, 1 of 1)

- [Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation](https://mlsanity.com/paper/2606.24672/) (2026)

## Abstract (arXiv)

We give two approximation algorithms solving the Stochastic Boolean Function Evaluation (SBFE) problem for symmetric Boolean functions. The first is an O(log n)-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.