It is known that testing whether a list of $n$ arbitrary real numbers is $\varepsilon$-close of being sorted (in Hamming distance) has query complexity $\Theta(\log n)$ [1]. It is also easy to show that if the function is Boolean-valued, then this becomes $\Theta(1/\varepsilon)$.

Recent work of Berman et al. [2] considers the same problem for sequences with elements in $[0,1]$, but with another distance (namely, a (normalized) $L_p$ distance instead of Hamming — the normalization being done to ensure the distances lie indeed in $[0,1]$). They show the query complexity then becomes $O(1/\varepsilon^p)$, for $p\in\{1,2\}$.

Now, does anyone know if any of these two variants has been considered (either Hamming or non-normalized $L_1$), but with the further restriction that the sequence has bounded $L_1$ norm? That is, decide (with high probability) whether a sequence of non-negative numbers $a_1,\dots, a_n$ with $\sum_{k=1}^{n} a_k = 1$ is (a) sorted or (b) $\varepsilon$-far from sorted?

I tried to find references, but so far didn't find any -- and want to make sure there is no prior work I'm unaware of before diving further into this (I am in particular interested in adaptive algorithms, as I (think I) have a non-adaptive tight bound for this question).

  1. Eldar Fischer. 2004. On the strength of comparisons in property testing.
  2. Berman, Raskhodnikova, and Yaroslavtsev. 2014. $L_p$-testing.
  • $\begingroup$ To be more precise, it is the $L_1$ case that I'm really interested in for this variation; I haven't thought much about the Hamming one, but I'd say the complexity is $\Theta(\log n)$, as in the (non-normalized) Hamming one. The lower bound on the query complexity should convey to this setting (up to a scaling of the hard instance), and the upper bound clearly holds (it is an easier problem as per the added constraint, so it is as most as hard). $\endgroup$
    – Clement C.
    Nov 19, 2014 at 11:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.