Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem

Lisa Hellerstein, Devorah Kletenik, Naifeng Liu +1

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…