Consider some problem $P$ and let's assume we sample the problem instance u.a.r. from some set $I$. Let $p$ be a lower bound on the distributional error of a deterministic algorithm on $I$, i.e., every deterministic algorithm fails on at least a $p$-fraction of the instances in $I$. [Edit: For a given instance $s \in I$, we use $P(s)$ to denote the set of correct solutions. We say that a deterministic algorithm $A$ fails on an instance $s$, if the output produced by $A$ given $s$ is not in $P(s)$.]

Does this also imply that every randomized algorithm $\mathcal{R}$ must fail with probability $p$ if, again, we sample the inputs u.a.r. from $I$?

My reasoning is as follows: Let $R$ be the random variable representing the random bits used by the algorithm. \begin{align} \Pr[ \text{$\mathcal{R}$ fails}] &= \sum_\rho \Pr[ \text{$\mathcal{R}$ fails and $R=\rho$}] \\ &= \sum_\rho \Pr[ \text{$\mathcal{R}$ fails} \mid R=\rho] \Pr[ R=\rho ] \\ &\ge p \sum_\rho \Pr[ R=\rho ] = p. \end{align} For the inequality, I used the fact that once we have fixed $R = \rho$, we effectively have a deterministic algorithm.

I can't find the flaw in my reasoning, but I would be quite surprised if this implication is true indeed.

  • 1
    $\begingroup$ What does it mean for a deterministic algorithm to fail? Since your question is quite a 'devil in the details' sort of question, you have to give some sort of formal definition of an algorithm that includes failure, because the standard definition (AFAIK) does not. Or at least it doesn't solve $P$, but some other problem you haven't defined. $\endgroup$
    – orlp
    Aug 25, 2020 at 11:10
  • $\begingroup$ @orlp: I've added more details. $\endgroup$ Aug 25, 2020 at 12:11
  • $\begingroup$ I'm pretty sure your definition leads to something undecidable or a contradiction. E.g. consider the deterministic algorithm that brute forces everything and checks for $P(s)$ before outputting. It never fails and is deterministic. $\endgroup$
    – orlp
    Aug 25, 2020 at 13:01
  • 1
    $\begingroup$ Right now the definition is a bit problematic since $I$ has to be finite (either you add a measure and talk about expectations, or you have no notion of "p-fraction") and in that case there is a deterministic algorithm which always answers correctly just by hardcoding the answers. You have a restrict the power of the algorithm to make it interesting, let us say we talk about some function $f:\{0,1\}^n\rightarrow\{0,1\}$ such that any polynomial circuit fails on at least a $p$-fraction. Adding randomness to the circuits, you can ask the same question, and your intuition is correct. $\endgroup$
    – Ariel
    Aug 25, 2020 at 14:57


Your Answer

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