Logarithmic lower-bound conjecture for monotonicity testing in the EVAL model
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Clément L. Canonne, “Big Data on the Rise: Testing monotonicity of distributions”, arXiv:1501.06783 (2015).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.