# Robustness to non-uniform randomness vs. one-sidedness

Consider any problem where, fixing two (disjoint) subsets $$\mathcal{Y},\mathcal{N}\subseteq \{0,1\}^n$$ of the input space, the goal is to obtain a randomized algorithm $$D$$ which, given a uniformly random bit string $$r$$, and on input $$x\in \{0,1\}^n$$, with probability at least $$2/3$$ over $$r$$,

1. outputs $$\mathsf{yes}$$ if $$x\in\mathcal{Y}$$;
2. outputs $$\mathsf{no}$$ if $$x\in\mathcal{N}$$.

Call any such $$D$$ a decider for $$(\mathcal{Y},\mathcal{N})$$.

(A natural example is property testing.) If further the first item (completeness) holds with probability one, then $$D$$ is one-sided.

Clearly, if $$D$$ is one-sided, then (1) holds even if $$r$$ comes from an arbitrary distribution, possibly chosen adversarially, instead of being uniform.

Let us say a decider for $$(\mathcal{Y},\mathcal{N})$$ is robust to bad coins if completeness (first item) degrades gracefully as the distribution $$R$$ of $$r$$ gets far from uniform. For instance, the probability that completeness holds only goes down linearly, as $$2/3-c\operatorname{d_{TV}}(R,U)$$ for some $$c\in[0,1)$$ .

My question is then:

Is the class of one-sided deciders a strict subset of deciders robust to bad coins? And has this been studied in some form?

(Also, the definition of robustness is quite open.. I went with total variation, but maybe something like min-entropy of $$R$$ makes more sense?)

Only one-sided deciders are robust to bad coins, under your definition; no other decider can be robust to bad coins. Let $$D$$ be a decider that is not one-sided. For $$x \in \mathcal{Y}$$, let $$\mathcal{W}_x = \{r \in \{0,1\}^m : D(x,r)=\textsf{no}\}$$ be the set of random strings $$r$$ such that $$D$$ outputs the wrong answer. Consider a distribution $$R$$ that, with probability $$1/3+\epsilon$$, picks $$r$$ uniformly at random from $$\mathcal{W}_x$$, and with probability $$2/3-\epsilon$$, picks $$r$$ uniformly at random from its complement. Then the decider is correct on $$x$$ with probability $$2/3 - \epsilon$$ when $$r$$ is chosen from $$R$$; yet $$d_{TV}(R,U) = \epsilon$$. So, there is no $$c \in [0,1)$$ with the desired property; you'd need to take $$c=1$$.

If you relax your definition to allow $$c \in [0,1]$$, so that (non-one-sided) deciders robust to bad coins exist, then the answer to your question is yes, it is a strict subset. It is not hard to come up with trivial examples. For instance, suppose that $$D$$ is correct for all choices of $$r$$ except for a single bad value $$r_\text{bad}$$; if $$r=r_\text{bad}$$, then $$D$$ is incorrect. This decider is robust to bad coins but is not a one-sided decider.

Moreover: with such an adjusted definition, every decider is robust to bad coins. By the definition of total variation distance and the definition of a decider,

$$\Pr_{r \in R}[\mathcal{W}_x] \le \Pr_{r \in U}[\mathcal{W}_x] + d_{TV}(R,U) \le 1/3 + d_{TV}(R,U),$$

so the probability that (1) holds is at least $$2/3 - d_{TV}(R,U)$$. Thus, $$D$$ is robust to bad coins with $$c = 1$$.

So, I think you need to re-consider your definition of "robust to bad coins". With your original formulation ($$c \in [0,1)$$), only one-sided deciders can ever meet it; with an adjusted formulation ($$c \in [0,1]$$), every decider meets it. In both cases, it collapses to be equivalent to some other existing notion. This suggests that we need a different definition.

• Reading your answer in detail as soon as possible, but in the first line, you mean "no (non-one-sided) decider is robust", right? Apr 4, 2019 at 19:51
• For one-sided testers, the set $\mathcal{W}_x$ is empty, so the distribution is not well-defined. Is it? Apr 4, 2019 at 20:11
• @ClementC., oops, you are absolutely right, I misunderstood what you were writing. My fault. I've edited my answer accordingly. Sorry about that.
– D.W.
Apr 4, 2019 at 20:14
• No worries. Also, after reading your answer (I had excluded $c=1$ indeed because of the very fact it makes everything robust), indeed it looks like it's not too interesting a concept per se -- though it gives a further motivation for one-sided testers. Thank you! Apr 4, 2019 at 20:18
• Is it allowed for a decider to output yes on $x\in\mathcal{Y}$ with probability strictly between $2/3$ and $1$? If so, it seems that $d_{TV}(R, U) > \varepsilon$ in such case. Apr 4, 2019 at 22:37