3
$\begingroup$

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.
$\endgroup$
  • $\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 '14 at 11:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.