How does one change the probability bounds in probabilistic complexity classes without changing the class? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:24:07Z https://cs.stackexchange.com/feeds/question/42149 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/42149 2 How does one change the probability bounds in probabilistic complexity classes without changing the class? user6818 https://cs.stackexchange.com/users/19847 2015-05-04T20:47:47Z 2015-05-04T21:12:40Z <p>I see this theorem whose proof is not clear to me : </p> <p>"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 &gt;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}$"</p> <ul> <li><p>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? </p></li> <li><p>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! </p></li> </ul> https://cs.stackexchange.com/questions/42149/-/42151#42151 2 Answer by Yuval Filmus for How does one change the probability bounds in probabilistic complexity classes without changing the class? Yuval Filmus https://cs.stackexchange.com/users/683 2015-05-04T21:12:40Z 2015-05-04T21:12:40Z <p>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 &gt; m/2] \geq \Pr[\operatorname{Bin}(m,1/2+\epsilon)&gt;m/2].$$ At this point you apply the Chernoff&ndash;Hoeffding bound. You take it from here.</p>