2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Reading your answer in detail as soon as possible, but in the first line, you mean "no (non-one-sided) decider is robust", right? $\endgroup$ – Clement C. Apr 4 at 19:51
  • $\begingroup$ For one-sided testers, the set $\mathcal{W}_x$ is empty, so the distribution is not well-defined. Is it? $\endgroup$ – Clement C. Apr 4 at 20:11
  • $\begingroup$ @ClementC., oops, you are absolutely right, I misunderstood what you were writing. My fault. I've edited my answer accordingly. Sorry about that. $\endgroup$ – D.W. Apr 4 at 20:14
  • $\begingroup$ 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! $\endgroup$ – Clement C. Apr 4 at 20:18
  • 1
    $\begingroup$ 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. $\endgroup$ – Sasha Kozachinskiy Apr 4 at 22:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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