# derandomize a BPP algorithm

Suppose we have a BPP algorithm $$A$$ s.t. its running time is random and is $$O(n^2)$$ in expectation. How do we create a new BPP algorithm $$B$$ to solve the same problem s.t. it has deterministic running time $$O(n^2)$$?

My effort: Denote the running time of $$A$$ as $$T$$. Suppose $$E(T)\leq T(n)=O(n^2)$$.

1. Run $$A$$ at most $$kT(n)$$ steps.
2. If it terminates, return its output; otherwise, output Yes with probability $$q$$.

But I just proved that this cannot be a BPP algorithm for any $$q$$... Any hint please?

• Your approach works. Nov 1 '20 at 6:23
• Note this is not what is usually referred to by derandomization. Nov 1 '20 at 6:24
• The algorithm $B$ is still randomized, and allowed to make mistakes. The only deterministic thing about it is its running time. Nov 1 '20 at 6:53

Derandomization is the process in which a randomized algorithm is converted to an equivalent deterministic algorithm. This is not what this exercise is asking you to do. The algorithm $$B$$ is still randomized – only its running time is deterministic.
Suppose that $$A$$ decides the problem $$L$$, in the following sense: if $$x \in L$$ then $$\Pr[A(x) = 1] \geq 2/3$$, and if $$x \notin L$$ then $$\Pr[A(x) = 0] \geq 2/3$$. Moreover, there is a function $$f(n) = O(n^2)$$ such that the expected running time of $$A$$ on $$x$$ is always at most $$f(|x|)$$. We want to construct a new algorithm $$B$$ with the same behavior regarding to $$L$$, and with the following additional property: there is a function $$g(n) = O(n^2)$$ such that the running time of $$B$$ on $$x$$ is exactly $$g(|x|)$$.
Suppose that $$f(n) = Cn^2$$, and consider your solution with $$K = 3C$$ and $$q=1/2$$. If we're careful, then there will exist a function $$g(n) = O(n^2)$$ such that the running time of $$B$$ on $$x$$ is exactly $$g(|x|)$$. What about the other property?
Suppose that $$x \in L$$ has size $$|x|=n$$. The expected running time of $$A$$ on $$x$$ is at most $$f(n) = Cn^2$$, and so $$A$$ terminates within $$Kn^2$$ steps with probability $$p \geq 2/3$$. If this happens, the probability that $$B$$ outputs $$1$$ is at least $$2/3$$. Otherwise, the probability that $$B$$ outputs $$1$$ is $$1/2$$. In total, $$\Pr[B(x) = 1] \geq p \cdot \frac{2}{3} + (1-p) \cdot \frac{1}{2} = \frac{1}{2} + p \cdot \frac{1}{6} \geq \frac{1}{2} + \frac{2}{3} \cdot \frac{1}{6} = \frac{11}{18} > \frac{1}{2}.$$ Similarly, if $$x \notin L$$ then $$\Pr[B(x) = 0] \geq 11/18$$. This is almost what we want – we want $$11/18$$ to be replaced by $$2/3$$.
In order to enhance the success probability ("error reduction"), we need to run $$A$$ several times and take a majority vote. By running $$A$$ enough times and by increasing the value of $$K$$, we get drive the error probability of $$B$$ down to any positive constant. Details left to you.