Logarithmic lower-bound conjecture for monotonicity testing in the EVAL model
Let be the size of the ordered domain and let be the distance parameter. In the model, a tester accesses a distribution through evaluation queries.
Logarithmic lower-bound conjecture. Monotonicity testing in the model has query complexity
The conjecture asserts that the logarithmic dependence on in the known upper bound is tight. The context gives lower bounds combining to , but does not establish the conjectured logarithmic dependence.
References
Primary source
Clément L. Canonne, “Big Data on the Rise: Testing monotonicity of distributions”, arXiv:1501.06783 (2015).
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.