Order-wise sample-complexity conjecture for monotone test functions
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.