2
$\begingroup$

I see this theorem whose proof is not clear to me :

"Let $L \subseteq \{0,1\}^*$ be a language and suppose that there exists a polynomial time PTM M such that for every $x \in \{0,1\}^*$ and $Pr[ M(x) = L(x) ] \geq 1/2 + \vert x \vert ^{-c}$ Then for every constant $d >0$ there exists a polynomial-time PTM M' such that for every $x \in \{0,1\}^*$, $Pr[M(x)=L(x)] \geq 1 - 2^{-\vert x \vert ^d}$"

  • Even if I assume this above theorem how does this help convert the $2/3$ probability guarantee in the definition of BPP , RP and coRP into $1-2^{-\vert x \vert ^d }$ without changing the class?

  • I understand that the above theorem is proven by doing a $8\vert x \vert ^{2c +d}$ iterations of the PTM's run and then taking the majority vote and somehow Chernoff bound helps get the exact numbers. But I can't understand the intermediate argument. It would be helpful if someone can help fill in!

Improve this question
$\endgroup$
2
  • $\begingroup$ This question is related cs.stackexchange.com/questions/18321/… $\endgroup$
    – Louis
    Commented May 4, 2015 at 20:55
  • $\begingroup$ Don't worry about the exact value $8n^{2c+d}$. Whatever bound you get is good enough as long as you're repeating the algorithm only polynomially many times. $\endgroup$
    – Yuval Filmus
    Commented May 4, 2015 at 21:13

1 Answer 1

Reset to default
2
$\begingroup$

Suppose that $\Pr[M(x) = L(x)] \geq 1/2 + \epsilon$. Run $M$ repeatedly $m$ times (for $m$ odd), and take the majority vote. Let $x_i$ be the indicator for the event that the $i$th run of $M$ gives the correct solution. The success probability of the majority vote algorithm is $$ \Pr[x_1+\cdots+x_m > m/2] \geq \Pr[\operatorname{Bin}(m,1/2+\epsilon)>m/2]. $$ At this point you apply the Chernoff–Hoeffding bound. You take it from here.

Improve this answer
$\endgroup$
7
  • $\begingroup$ What is $Bin$ here? So what exactly does the Chernoff bound give in this case? Is the whole point that to show that given any probability threshold one can iterate the stuff a certain number of times to get the soundness probability below this threshold? $\endgroup$
    – user6818
    Commented May 7, 2015 at 22:08
  • $\begingroup$ $\operatorname{Bin}(n,p)$ is a binomial random variable corresponding to $n$ trials with success probability $p$ each. In order to know that the Chernoff bound gives in this case, you take the formula given by the Chernoff bound, substitute the parameters, and simplify. You don't need me for that. $\endgroup$
    – Yuval Filmus
    Commented May 7, 2015 at 22:38
  • $\begingroup$ I mean - why is the Chernoff-Hoefding bound necessary? Think of it this way : Say success probability in a trial is lower bounded by $p$ then the probability that $k$ of the $n$ trials succeed is lower bounded by $(1-p)^{(n-k) }p^k$. So one can define the function $f(n) = \text{ probability that most of the n trials succeed}$ and one gets that $f(n) \geq \sum_{k= \frac{n}{2}}^{n} (1-p)^{(n-k)}p^k$. Given a need for a success quarantee of $q$ one would be done if one can show that there exists a $n$ such that $q < \sum_{k= \frac{n}{2}}^{n} (1-p)^{(n-k)}p^k $ . $\endgroup$
    – user6818
    Commented May 8, 2015 at 0:27
  • $\begingroup$ Why is this not the right way to think? Why do Chernoff-Hoefding? $\endgroup$
    – user6818
    Commented May 8, 2015 at 0:27
  • $\begingroup$ It is the right way to think. Chernoff's bound is just a convenient way of estimating this sum. If you can estimate the sum in some other way, that's also great. $\endgroup$
    – Yuval Filmus
    Commented May 8, 2015 at 0:29

Your Answer

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

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