2
$\begingroup$

An $\epsilon$-tester given an input and a property, is defined as follows:
If the input holds the property then the tester should accept with probability at least $\frac 2 3$. Otherwise if the input is more than $\epsilon$ far from holding the property then the tester should reject with probability at least $\frac 2 3$. Meaning that if the input holds the property, with $f$ being less than $\epsilon$ far from not holding the property, the algorithm should accept with probability at least $\frac 2 3$. If we need to change at least ϵn values of $f$ in order to obtain a function satisfying the property then the algorithm should reject with probability at least $\frac 2 3$.

A tester with one-sided error is a tester, given an input, if the input holds the property then the tester accepts the input with probability 1.

A 2-injective function $f\colon [2n] \to [n]$ is a function such that for all $1 \leq k \leq n$ there exist $1 \leq i<j \leq 2n$ such that $f(i) = f(j)=k$ and there is no other $l \neq i,j $ such that $ f(l)=k $. Here $[m]$ for $m\ge1$ is the set of first $m$ positive integers, $\{1,2,\cdots, m\}$.

We can check that $f$ has more than $\epsilon$ of the input that do not hold the property iff $$\frac{2\left|\{k\in[n]: f^{-1}(k)=\emptyset\}\right| + \left|\{k\in[n]: |f^{-1}(k)|=1\}\right|}{2n} \gt \epsilon$$

We need to show that there exists $\epsilon$, for which an $\epsilon$-tester with one-sided error of a function $f\colon [2n] \to [n]$ for the "2-injective" property, requires $\Omega(n^{2/3})$ queries.

Unfortunately, searching online for articles and scientific papers about the topic yielded nothing, and I haven't had any success in solving this question myself. I managed only to show it for injective functions but the proof is almost straight-forward and trivial.

I'm pretty new at the field of property-testing so any help would be highly appreciated!

$\endgroup$
10
  • 2
    $\begingroup$ Similar question. Where do they all come from? $\endgroup$ Jun 25, 2022 at 17:00
  • $\begingroup$ "Meaning that if the input holds the property, with up to ϵn input's elements that do not, the algorithm accepts should accept with probability at least 2/3. If more than ϵn of the input's elements do not hold the property then the algorithm should reject with probability at least 2/3." I'm not sure what this means. What does this mean for your particular condition? $\endgroup$ Jun 25, 2022 at 17:03
  • $\begingroup$ I encourage you to share the context where you encountered this problem, or the motivation. Also, please see cs.stackexchange.com/questions/152488/…. $\endgroup$
    – D.W.
    Jun 26, 2022 at 1:02
  • $\begingroup$ @YuvalFilmus I'm sorry I didn't express myself right. As I said, I'm new to the field of property testing with prob. algorithm, hence my knowledge in this field is very limited and narrow. $\endgroup$
    – AK-23
    Jun 27, 2022 at 13:23
  • $\begingroup$ @D.W. These questions are all from my course's book about prob. testers, as I'm a M.sc. student. Just for fun knowledge, I'm enrolled to the course as a free listener but I try hard to solve all questions by myself. $\endgroup$
    – AK-23
    Jun 27, 2022 at 13:24

1 Answer 1

2
$\begingroup$

Here's a sketch, for $\epsilon=1/10$ or so.

Let $f$ be a $2$-injective function chosen uniformly at random, and let $\widetilde{f}$ be the perturbation of $f$ formed by choosing $Y_1 \subseteq [n], |Y_1| = n/10$ uniformly at random, then choosing $Y_2 \subseteq [n]\setminus Y_1, |Y_2| = n/10$ uniformly at random, then choosing a bijection $\phi : Y_2 \to Y_1$ uniformly at random, then, for each $y_2 \in Y_2$, choosing $x_{y_2} \in f^{-1}(y_2)$ uniformly at random, and setting $\widetilde{f}(x) := f(x)$ if $x$ is not in $\{x_{y_2} : y_2 \in Y_2\}$ and $\widetilde{f}(x) := \phi(y_2)$ if $x = x_{y_2}$ for some $y_2 \in Y_2$.

We'll present the presented tester with either $f$ or $\widetilde{f}$, each chosen with probability $1/2$.

Since there's no relation amongst the points of $[2n]$ (i.e. they are all the essentially the same and learning the value of the function at one point tells you equally about the value of the function at the other points), the set of points that the presented tester queries is as good as a set of points chosen uniformly at random from $[2n]$.

If the number of queries is less than $n^{2/3}$, say $n^{2/3-\delta}$, and $\widetilde{f}$ is presented to the tester, then, for any given $y \in Y_1$, the probability that you see $y$ outputted by three of the queried points is basically $n^{-1-3\delta}$, so union bounding over $Y_1$ shows that it is very unlikely you learn that any point has preimage of size $3$. So (here is where some more arguments need to be added) the tester can't tell $f$ and $\widetilde{f}$ apart.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.