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

From papers

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

Ω(lognε).\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(logn/loglogn,1/ε))\Omega\left(\max\left(\log n/\log\log n,1/\varepsilon\right)\right), 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

No solutions have been posted yet.