0
$\begingroup$

The following is a well-known result of BPP in complexity theory, e.g., Theorem 1 and its proof from here:

Consider a probabilistic Turing Machine (PTM) $M$, and a language $L \in BPP$:

  1. If $x \in L$ (YES instance), then $M$ outputs YES with probability $\geq 1/2 + 1 / poly(n)$,

  2. If $x \notin L$ (NO instance), then $M$ outputs NO with probability $\leq 1/2 - 1 / poly(n)$.

We can amplify the success probability of $M$ to $1 - \frac{1}{2^{q(n)}}$, for some polynomial $q(n)$. This can be shown by running the PTM $M$ for a total of polynomial times, taking the majority vote, and using the Chernoff bound.

If I am not mistaken, this result also implies that the new PTM $M'$ from the procedure above has the probability gap of some constant (for instance, it's $2 / poly(n)$ for $M$).

My question: This result leads to me thinking that what would happen if we have $1/2 + 1 / \exp(n)$ instead of only $poly(n)$? Can we also run it for polynomial times, take the majority vote, and then use some tail bounds and concentration inequalities to show that the new probability gap from the new PTM is $t(n) / \exp(n)$ for some polynomial $t(n)$?

My progress: I don't achieve much success with the traditional Chernoff bounds, I also read some results but am not sure if they are really helpful. This survey by Fan Chung and Linyuan Lu also mentioned martingales, do you think it could be helpful here?

Thank you for your time!

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ When the probability is that small, you get an (apparently) much stronger complexity class, PP. See the complexity zoo for an idea of how much more powerful PP seems to be than BPP. Intuitively, just taking poly(n) samples is not enough to distinguish two 0-1 random variables with probabilities that are only 1/exp(n) apart; you need exp(n) samples for there to be a decent chance that the two random variables actually take different values in some sample. $\endgroup$
    – Ryan Williams
    Sep 23 at 14:49

0

Reset to default

Your Answer

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