Robustness to non-uniform randomness vs. one-sidedness

Question

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?)

Answer 1

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.