Timeline for Practical use of probability amplification for randomized algorithms
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10, 2010 at 17:25 | comment | added | Suresh Venkat | argghh. sorry. Thanks for the correction. | |
| Aug 10, 2010 at 16:44 | comment | added | Ryan Williams | Suresh: you can replace the error with inverse-exponential in poly(n). In fact the proofs of several results in complexity rely on this, such as Adleman's theorem. It doesn't imply PP=BPP because, in the process of making the error probability very low, you have also introduced poly(n) new random bits. So even if the probability of error becomes 1/2^{n^k}, there will be 2^{poly(n^k)} possible random bit strings. So you still cannot count exactly, or even close to that. | |
| Aug 10, 2010 at 10:36 | comment | added | Marcos Villagra | actually, it doesn't say that we can replace an inverse polynomial by an inverse exponential. | |
| Aug 10, 2010 at 9:01 | comment | added | Marcos Villagra | In Arora and Barak, theorem 7.10 page 132 it says Let $L\subseteq\{0,1\}^*$ be a language and suppose there exists a polynomial-time PTM M s.t. for every $x\in \{0,1\}^*$, $Pr[M(x)=L(x)]\geq 1/2+n^{-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^{-n^d}$. Is my interpretation correct? Of course it's not saying anything about the running time. | |
| Aug 10, 2010 at 8:48 | history | answered | Suresh Venkat | CC BY-SA 2.5 |