Non-Adaptive Evaluation of k k -of- n n Functions: Tight Gap and a Unit-Cost PTAS
Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior · 2025
Read Non-Adaptive Evaluation of k k -of- n n Functions: Tight Gap and a Unit-Cost PTAS by Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-05877.txt.
Introduction
Mads Anker Nielsen, Lars Rohwedder, and Kevin Schewior study fixed test plans for threshold questions under uncertainty, in this 2025 paper. Each test costs money and reveals a yes or no fact with known odds. The goal is to learn whether at least k of n facts are yes, at least expected cost, with the whole plan set in advance.
First, they prove a tight bound: set plans can cost at most twice the best flexible plan, closing a long gap. Second, for equal test costs they give an approximation scheme that runs in polynomial time. The core trick guesses landmark tests in chosen buckets. The scheme extends to all symmetric threshold rules.
Catalog record
| CREATOR | Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-05877
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Non-Adaptive Evaluation of k k -of- n n Functions: Tight Gap and a Unit-Cost PTAS Thanks: Supported in part by the Independent Research Fund Denmark, Natural Sciences, grant DFF-4283-00079B. Mads Anker Nielsen, Lars Rohwedder, Kevin Schewior Abstract We consider the Stochastic Boolean Function Evaluation (SBFE) problem in the well-studied case of k k -of- n n functions: There are independent Boolean random variables x 1 , … , x n x_{1},\dots,x_{n} where each variable i i has a known probability p i p_{i} of taking value 1 1 , and a known cost c i c_{i} that can be paid to find out its value. The value of the function is 1 1 iff there are at least k k 1 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 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 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. 1 Introduction The Stochastic Boolean Function Evaluation (SBFE) problem is a fundamental problem in stochastic combinatorial optimization, see e.g. the survey by Ünlüyurt [ 24 ] or the more recent works [ 6 , 9 , 16 ] . A function f:\{0,1\}^{n}\to\{0,1\} is given (typically in compact representation), and the task is to find out f(x_{1},\dots,x_{n}) where x_{1},\dots x_{n} are independent Boolean random variables. For each i\in[n] , p_{i}\in(0,1) is the known probability that x_{i}=1 , and the value of x_{i} can be learned by a policy at known cost c_{i}\geq 0 . There are two fundamental paradigms for policies: the adaptive one and the non-adaptive one. An adaptive policy may make decisions to test variables depending on the outcomes of previous tests, i.e., it can be viewed as a decision tree. A non-adaptive policy, in contrast, is simply specified by an order of variables to test, which may not be adapted depending on the outcomes of tests. In either case, policies are evaluated by the expected cost paid until the value of f is determined (with probability 1 ). While non-adaptive policies have a simple representation, are easy to execute, and are therefore often desirable from a practical point of view, they are generally subobtimal. The adaptivity gap [ 5 , 14 ] of a class of functions measures the severity of precisely this suboptimality: the worst-case (in this class of functions) multiplicative gap between the expected cost of the best non-adaptive policy and that of the best adaptive policy. An important class of functions are k -of- n functions. Such a function is simply given by an integer k\in[n] , and the function value is 1 if and only if there are at least k 1 s among the input variables, i.e., x_{1}+\cdots+x_{n}\geq k . SBFE has also been considered for a number of more general classes of functions, e.g., linear threshold functions [ 6 , 18 , 9 ] , symmetric Boolean functions [ 11 , 9 , 20 , 21 ] , and voting functions [ 16 ] . For many of these classes, polynomial-time approximation algorithms to compute the best non-adaptive or adaptive policy have been proposed. Apart from it occurring as a special case of many SBFE problems studied in the literature, another reason for the popularity of k -of- n functions may be the elegance of the optimal policy [ 22 , 2 ] : Conditional on function value 0 and 1 , it is optimal to test in increasing order of c_{i}/(1-p_{i}) and c_{i}/p_{i} ratios, respectively, to find a certificate at minimum expected cost. Since these policies need to test at least n-k+1 and k tests, respectively, to find a certificate, there is, by the pigeon-hole principle, some test occurring in both these prefixes, which can safely be tested even in the original (unconditional) case. When non-adaptive policies come into play, however, much less is known. First, while it is known that, in the unit-cost case the adaptivity gap is exactly 3/2 [ 12 , 21 ] , no stronger lower bound for the general case is known, with the upper bound only being 2 [ 10 ] . Second, the polynomial-time approximation algorithms implied by the upper-bound proofs on the adaptivity gaps are those with the best known approximation ratios, i.e., 3/2 in the unit-cost case and 2 in the general case. In this paper, we make significant progress on both questions. 1.1 Our Contribution Our first result is the following. Theorem 1 . The adaptivity gap of SBFE on k -of- n functions is exactly 2 . This settles an open question that had been known within the community and is explicitly stated in [ 21 ] . Since an upper bound of 2 was known [ 10 ] , our contribution is showing a matching lower bound. Our construction is perhaps surprisingly simple. To give an overview, let us first recall the class of instances for the unit-cost version which leads to a lower bound of 3/2 [ 21 ] . Here, n=2t+1 for some integer t , and k=t+1 . There are t 1 -variables taking value 1 and t 0 -variables taking value 0 . Note that we do not allow probabilities of precisely 0 or 1 in our model, but we do in this section for the simplicity of exposition. Such variables still have to be tested in order to use them towards certifying the function value. In addition, there is a single pivotal variable with probability 1/2 , whose value thus determines the function value. An adaptive policy can simply test the pivotal variable, having, say, value i , and then test all the i -variables, at expected cost of t+1 . A non-adaptive policy, on the other hand, can only “guess” the outcome of the pivotal variable, resulting in an expected cost of \nicefrac{{3}}{{2}}\cdot t+1 . Then taking the limit t\to\infty yields the result. Note that, in the arbitrary-cost case, we can simply assign the pivotal variable a cost of 0 , so that t=1 would actually suffice to obtain a bound of 3/2 . The main idea of our construction is to have several, say, m , pivotal variables, all with probability 1/2 and cost 0 . It is easy to see that, with t=1 , the resulting ratio is still 3/2 . The correct regime turns out to be the one in which t is large but m is much larger