# Generalization of Element Distinctness

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

• 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. – Clement C. Jul 18 '19 at 0:07
• 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. – Clement C. Jul 18 '19 at 0:09
• Don't you mean $|f^{-1}({i})| = r$ for all $i \in [n]$? – smapers Jul 18 '19 at 5:36
• @smapers Gosh yes, sorry for the blunder. Fixed, thanks! – Clement C. Jul 18 '19 at 5:41