Order-wise sample-complexity conjecture for monotone test functions
Let be a monotone test function, let denote the corresponding function appearing in the sample-complexity bounds, and let denote the corresponding quantity optimized over . In the sparse regime with and , the sample-complexity bounds are expressed in terms of these quantities.
Sample-complexity conjecture. For any monotone test function ,
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
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.