{"ID":2896989,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.05877","arxiv_id":"2507.05877","title":"Non-Adaptive Evaluation of $k$-of-$n$ Functions: Tight Gap and a Unit-Cost PTAS","abstract":"We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of $k$-of-$n$ functions: There are independent Boolean random variables $x_1,\\dots,x_n$ where each variable $i$ has a known probability $p_i$ of taking value $1$, and a known cost $c_i$ that can be paid to find out its value. The value of the function is $1$ iff there are at least $k$ $1$s among the variables. The goal is to efficiently compute a strategy that, at minimum expected cost, tests the variables until the function value is determined. While an elegant polynomial-time exact algorithm is known when tests can be made adaptively, we focus on the non-adaptive variant, for which much less is known. First, we show a clean and tight lower bound of $2$ on the adaptivity gap, i.e., the worst-case multiplicative loss in the objective function caused by disallowing adaptivity, of the problem. This improves the tight lower bound of $3/2$ for the unit-cost variant. Second, we give a PTAS for computing the best non-adaptive strategy in the unit-cost case, the first PTAS for an SBFE problem. At the core, our scheme establishes a novel notion of two-sided dominance (w.r.t. the optimal solution) by guessing so-called milestone tests for a set of carefully chosen buckets of tests. To turn this technique into a polynomial-time algorithm, we use a decomposition approach paired with a random-shift argument. In fact, our PTAS extends to the class of arbitrary symmetric Boolean functions, which are Boolean functions whose value only depends on the number of $1$s among the input variables.","short_abstract":"We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of $k$-of-$n$ functions: There are independent Boolean random variables $x_1,\\dots,x_n$ where each variable $i$ has a known probability $p_i$ of taking value $1$, and a known cost $c_i$ that can be paid to find out its value....","url_abs":"https://arxiv.org/abs/2507.05877","url_pdf":"https://arxiv.org/pdf/2507.05877v2","authors":"[\"Mads Anker Nielsen\",\"Lars Rohwedder\",\"Kevin Schewior\"]","published":"2025-07-08T10:59:59Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[\"Generative Adversarial Network\"]","has_code":false}