Logarithmic lower-bound conjecture for monotonicity testing in the EVAL model

About 11 years old · traced to

Let nn be the size of the ordered domain and let ε>0\varepsilon>0 be the distance parameter. In the EVAL{\sf EVAL} model, a tester accesses a distribution through evaluation queries.

Logarithmic lower-bound conjecture. Monotonicity testing in the EVAL{\sf EVAL} model has query complexity

Ω(log⁡nε).\Omega\left(\frac{\log n}{\varepsilon}\right).

The conjecture asserts that the logarithmic dependence on nn in the known upper bound is tight. The context gives lower bounds combining to Ω(max⁡(log⁡n/log⁡log⁡n,1/ε))\Omega\left(\max\left(\log n/\log\log n,1/\varepsilon\right)\right), 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.