English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the Stochastic Boolean Function Evaluation (SBFE) problem wherethe task is to efficiently evaluate a known Boolean function $f$ on an unknownbit string $x$ of length $n$. We determine $f(x)$ by sequentially testing thevariables of $x$, each of which is associated with a cost of testing and anindependent probability of being true. If a strategy for solving the problem isadaptive in the sense that its next test can depend on the outcomes of previoustests, it has lower expected cost but may take up to exponential space tostore. In contrast, a non-adaptive strategy may have higher expected cost butcan be stored in linear space and benefit from parallel resources. Theadaptivity gap, the ratio between the expected cost of the optimal non-adaptiveand adaptive strategies, is a measure of the benefit of adaptivity. We presentlower bounds on the adaptivity gap for the SBFE problem for popular classes ofBoolean functions, including read-once DNF formulas, read-once formulas, andgeneral DNFs. Our bounds range from $\Omega(\log n)$ to $\Omega(n/\log n)$,contrasting with recent $O(1)$ gaps shown for symmetric functions and linearthreshold functions.

Adaptivity Gaps for the Stochastic Boolean Function Evaluation Problem