Order-wise sample-complexity conjecture for monotone test functions

About 5 years old · traced to

Let f(⋅)f(\cdot) be a monotone test function, let h(f)h(f) denote the corresponding function appearing in the sample-complexity bounds, and let Γ(q)\Gamma(q) denote the corresponding quantity optimized over q∈(0,1)q\in(0,1). In the sparse regime with d=nθd=n^\theta and 0≤θ<10\leq\theta<1, the sample-complexity bounds are expressed in terms of these quantities.

Sample-complexity conjecture. For any monotone test function f(⋅)f(\cdot),

min⁡q∈(0,1)Γ(q)h(f)dlog⁡n∈Θ(1).\frac{\min_{q\in(0,1)}\Gamma(q)}{h(f)d\log n}\in\Theta(1).

A positive resolution would tightly characterize the order-wise sample complexity for every monotone test function, extending the order-wise tightness already established for noisy test functions. The supplied text does not indicate whether this conjecture has been resolved.

References

Primary source

Xiwei Cheng, Sidharth Jaggi and Qiaoqiao Zhou, “Generalized Group Testing”, arXiv:2102.10256 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.