Order-wise sample-complexity conjecture for monotone test functions

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),

minq(0,1)Γ(q)h(f)dlognΘ(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.

Sources & referencesView supporting material

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.