We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $n > N_c$, $$\epsilon(n)<\frac{1}{n^c}$$ (From wikipedia)

Assume that two probabilistic polynomial-time algorithms $O_{1},O_{2}$ satisfy that $$ \Sigma_{y \in \{\, 0,1 \,\}}\left\vert \mathrm{Pr}\left[ O_{1}(x) = y \right] - \mathrm{Pr}\left[ O_{2}(x) = y \right] \right\vert \leq \epsilon_{1}(n) $$ for all $x$, where $\left\vert x \right\vert = n$ and $\epsilon_{1}$ is negligible.

Let $A$ be a probabilistic polynomial-time algorithm. Can we get that $$ \Sigma_{y \in \{\, 0,1 \,\}}\left\vert \mathrm{Pr}\left[ A^{O_{1}}(x) = y \right] - \mathrm{Pr}\left[ A^{O_{2}}(x) = y \right] \right\vert \leq \epsilon_{2}(n) $$ for all $x$? Where $\left\vert x \right\vert = n$ and $\epsilon_{2}$ is negligible.

  • $\begingroup$ What are probabilistic polynomial time oracles? Where is the randomness in your first statement? The statement would make sense if you replace the word oracle with the word machine, but in that case the second statement requires modification. $\endgroup$ – Ariel Nov 24 '17 at 10:45
  • $\begingroup$ @Ariel I mean $O_{1},O_{2}$ are also probabilistic polynomial-time algorithms. So should I change 'oracles' to 'algorithms' or 'Turing machines'? $\endgroup$ – TeamBright Nov 24 '17 at 11:04
  • $\begingroup$ When we say oracles, we're usually talking about languages, a machine with an access to an oracle is a machine which can raise queries of the form "is this string in the language?". Thus, it is not clear what is meant by probabilistic polynomial time oracles, since ppt is a property of a machine and not a language. If now $O_1,O_2$ are machines, then you need to be clear about what you mean by $A^{O_1}$, since $O_1$ may reply differently to the same query depending on its randomness. $\endgroup$ – Ariel Nov 24 '17 at 11:13
  • $\begingroup$ Perhaps you mean to say that $A$ is a ppt algorithm which simulates another ppt machine during its computation, and you wish to know how the acceptance probability varies between simulating $O_1$ and $O_2$. In that case your notation is fine, but you have to mention this, since the standard way to interpret $A^B$ is that $B$ is a language and $A$ is machine which queries membership to $B$, if $B$ is a machine then it is not always clear (as is in this case) what language you want to associate with it. $\endgroup$ – Ariel Nov 24 '17 at 11:16
  • $\begingroup$ Use a "hybrid argument", if you know what that means (it comes from the crypto literature). $\endgroup$ – D.W. Nov 24 '17 at 23:23

Given $x$, define $p_1(x,y) = \Pr[O_1(x) = y]$ and $p_2(x,y) = \Pr[O_2(x) = y]$. Let $$ \begin{align*} \delta_x &= \sum_y [\max(p_1(x,y),p_2(x,y)) - \min(p_1(x,y),p_2(x,y))] \\ &= \sum_y |p_1(x,y) - p_2(x,y)| \\ &\leq \epsilon_1(n). \end{align*} $$ On the other hand, $$ \sum_y [\max(p_1(x,y),p_2(x,y)) + \min(p_1(x,y),p_2(x,y))] = \sum_y [p_1(x,y) + p_2(x,y)] = 2. $$ Therefore $$ \sum_y \min(p_1(x,y),p_2(x,y)) = 1 - \frac{\delta_x}{2}. $$ Consider now the following random process that generates two random variables $R_1,R_2$:

  • For every $y$, with probability $\min(p_1(x,y),p_2(x,y))$, generate $R_1=R_2=y$.
  • Otherwise (this happens with probability $\delta_x/2$):
    1. For every $y$, with probability $\frac{p_1(x,y)-\min(p_1(x,y),p_2(x,y))}{\delta_x/2}$ generate $R_1=y$.
    2. For every $y$, with probability $\frac{p_2(x,y)-\min(p_1(x,y),p_2(x,y))}{\delta_x/2}$ generate $R_2=y$.

This process is a coupling that generates two random variables $R_1,R_2$ with the following properties:

  1. $R_1 \sim O_1(x)$.
  2. $R_2 \sim O_2(x)$.
  3. $\Pr[R_1 \neq R_2] = \delta_x \leq \epsilon_1(n)$.

Let us go back to your algorithm $A$, and suppose that it runs in time $T(n)$. Use the coupling above to generate two random variables $B_1,B_2$ with the following properties:

  1. $B_1 \sim A^{O_1}(x)$.
  2. $B_2 \sim A^{O_2}(x)$.
  3. $\Pr[B_1 \neq B_2] \leq T(n) \epsilon_1(n) =: \epsilon_2(n)$.

Note that $\epsilon_2(n)$ is negligible. We have

$$ \begin{align*} &\sum_y |\Pr[A^{O_1}(x) = y] - \Pr[A^{O_2}(x) = y]| \\ = &\sum_y |\Pr[B_1 = y] - \Pr[B_2 = y]| \\ = &\Pr[B_1 \neq B_2] \sum_y |\Pr[B_1=y|B_1 \neq B_2] - \Pr[B_2=y|B_1 \neq B_2]| \\ \leq &\Pr[B_1 \neq B_2] \sum_y (\Pr[B_1=y|B_1 \neq B_2] + \Pr[B_2=y|B_1 \neq B_2]) \\ \leq &2\epsilon_2(n), \end{align*} $$ since given $\Pr[B_1=y|B_1=B_2] = \Pr[B_2=y|B_1=B_2]$.

| cite | improve this answer | |

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.