5
$\begingroup$

In the element distinctness problem, one has query access to an arbitrary multiset of $n$ elements and must decide whether they are all distinct.

From a property testing point of view, the question is:

Given parameter $\varepsilon > 0$ and query access to $f\colon[n] \to [n]$, distinguish with probability $2/3$ between (i) $f$ is a bijection (all elements are distinct), and (ii) $|f([n])| < (1-\varepsilon) n$ (the list has less than $(1-\varepsilon) n$ distinct elements).

This question was first studied in [1], and its query complexity is known to be $\Theta(\sqrt{n/\varepsilon})$ (see also the lecture notes [2,3]).

I am wondering if the following generalization has been studied:

Given parameter $\varepsilon > 0$ and query access to $f\colon[m] \to [n]$ such that $r := \frac{m}{n} \in\mathbb{N}$, distinguish with probability $2/3$ between

(i) $|f^{-1}(\{i\})| = r$ for all $i\in[n]$ , and

(ii) at least $\varepsilon m$ values of $f$ must be changed for it to satisfy (i)

(the element distinctness problem is the specific case $r=1$)


[1] F. Ergün, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan, Spot checkers, Journal of Computer and System Science 60 (2000), 717–751.

[2] P. Beame, Introduction to Sublinear Algorithms (Lecture 1), 2014. https://courses.cs.washington.edu/courses/cse522/14sp/lectures/lect01.pdf

[3] R. Krautgamer, Seminar on Sublinear Time Algorithms (Lecture 5, scribed by Anat Ganor), 2010. http://www.wisdom.weizmann.ac.il/~robi/teaching/2010b-SeminarSublinearAlgs/scribe5.pdf

$\endgroup$
  • $\begingroup$ Note: there is an immediate $O(\sqrt{n}/\varepsilon^2)$ (two-sided) upper bound, from a reduction to the uniformity testing problem (in distribution testing), as querying uniform indices in $f$ corresponds to sampling from the induced empirical distribution (which is uniform for (i), and $\varepsilon$-far from it in (ii)). One can improve bit this bound to get something better (when $r < 1/\varepsilon$), $O(\min(\sqrt{n}/\varepsilon^2, r\sqrt{n}/\varepsilon))$, but that is a two-sided, sample-based tester which ignores a lot of the available information given by the queries. $\endgroup$ – Clement C. Jul 18 at 0:07
  • $\begingroup$ So I am specifically asking about the query complexity of this problem, which should be strictly lower (in some parameter regimes) than this weak upper-bound-via-reduction. $\endgroup$ – Clement C. Jul 18 at 0:09
  • $\begingroup$ Don't you mean $|f^{-1}({i})| = r$ for all $i \in [n]$? $\endgroup$ – smapers Jul 18 at 5:36
  • $\begingroup$ @smapers Gosh yes, sorry for the blunder. Fixed, thanks! $\endgroup$ – Clement C. Jul 18 at 5:41

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.