<p>In the element distinctness problem, one has query access to an arbitrary multiset of <span class="math-container">$n$</span> elements and must decide whether they are all distinct.</p>
<p>From a property testing point of view, the question is:</p>
<blockquote>
<p>Given parameter <span class="math-container">$\varepsilon &gt; 0$</span> and query access to <span class="math-container">$f\colon[n] \to [n]$</span>, distinguish with probability <span class="math-container">$2/3$</span> between (i) <span class="math-container">$f$</span> is a bijection <em>(all elements are distinct)</em>, and (ii) <span class="math-container">$|f([n])| &lt; (1-\varepsilon) n$</span> <em>(the list has less than <span class="math-container">$(1-\varepsilon) n$</span> distinct elements)</em>.</p>
</blockquote>
<p>This question was first studied in [1], and its query complexity is known to be <span class="math-container">$\Theta(\sqrt{n/\varepsilon})$</span> (see also the lecture notes [2,3]).</p>
<p>I am wondering if the following generalization has been studied:</p>
<blockquote>
<p>Given parameter <span class="math-container">$\varepsilon &gt; 0$</span> and query access to <span class="math-container">$f\colon[m] \to [n]$</span> such that <span class="math-container">$r := \frac{m}{n} \in\mathbb{N}$</span>, distinguish with probability <span class="math-container">$2/3$</span> between</p>
<p>(i) <span class="math-container">$|f^{-1}(\{i\})| = r$</span> for all <span class="math-container">$i\in[n]$</span> , and</p>
<p>(ii) at least <span class="math-container">$\varepsilon m$</span> values of <span class="math-container">$f$</span> must be changed for it to satisfy (i)</p>
</blockquote>
<p>(the element distinctness problem is the specific case <span class="math-container">$r=1$</span>)</p>
<hr />
<p>[1] F. Ergün, S. Kannan, R. Kumar, R. Rubinfeld, and M. Viswanathan, <em>Spot checkers</em>, Journal of Computer and System Science 60 (2000), 717–751.</p>
<p>[2] P. Beame, Introduction to Sublinear Algorithms (Lecture 1), 2014. <a href="https://courses.cs.washington.edu/courses/cse522/14sp/lectures/lect01.pdf" rel="nofollow noreferrer">https://courses.cs.washington.edu/courses/cse522/14sp/lectures/lect01.pdf</a></p>
<p>[3] R. Krautgamer, Seminar on Sublinear Time Algorithms (Lecture 5, scribed by Anat Ganor), 2010. <a href="http://www.wisdom.weizmann.ac.il/%7Erobi/teaching/2010b-SeminarSublinearAlgs/scribe5.pdf" rel="nofollow noreferrer">http://www.wisdom.weizmann.ac.il/~robi/teaching/2010b-SeminarSublinearAlgs/scribe5.pdf</a></p>

CC BY-SA 4.0
2019-07-18T00:07:44.447Z
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.
CC BY-SA 4.0
2019-07-18T00:09:30.823Z
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.
CC BY-SA 4.0
2019-07-18T05:36:30.233Z
Don't you mean $|f^{-1}({i})| = r$ for all $i \in [n]$?
smapers
CC BY-SA 4.0
2019-07-18T05:41:10.763Z
@smapers Gosh yes, sorry for the blunder. Fixed, thanks!
Clement C.
<reference-request><property-testing>
Generalization of Element Distinctness
Clement C.
# Generalization of Element Distinctness

(Asked by: username_0 on 2019-07-17)

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](http://www.wisdom.weizmann.ac.il/%7Erobi/teaching/2010b-SeminarSublinearAlgs/scribe5.pdf)

**Tags:** reference-request, property-testing
> **Comments:**
> **username_0**: 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.  
> **username_0**: 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.  
> **username_1**: Don't you mean $|f^{-1}({i})| = r$ for all $i \in [n]$?  
> **username_0**: @smapers Gosh yes, sorry for the blunder. Fixed, thanks!  

---

## 0 answers

