| Your sketch is correct, but what you're describing is not derandomization. It is "accuracy amplification" by repeating the test. Each round of the test uses more random bits, right? So you're converting more random bits into arbitrary confidence. The objective of derandomization is to completely remove the need to flip random bits from the algorithm. If you had a deterministic PRG, you could completely remove the error from a BPP algorithm. Here is a sketch of why, where I'm eliding the quantitative details: A PRG takes as input a short string of truly random bits (a "seed") and produces as output a long string of "pseudorandom bits". By the definition of a PRG, an efficient algorithm cannot tell the different between the PRG's output and a long string that was really sampled uniformly at random. So, the obvious way to use this to derandomize a BPP machine M is to toss a small number of random bits, run them through the PRG, and use the output of the PRG as the random bits that M would use. We've used the PRG to shrink the amount of randomness required, but not completely eliminate it. To fully eliminate the randomness, brute-force over every possible seed, run M on an input x with each PRG output serving as the random coins, and take the majority vote. This is a fully deterministic process. It is efficient if the ratio between the seed length of the PRG and output length of the PRG is such that 2^(seed length) is still polynomial. The strategy is always correct because, if there is an input y where this brute-force-and-vote strategy fails to produce the correct answer, we can use that input to produce an efficient algorithm that distinguishes between PRG outputs and truly random strings. Why? Because on random bit-strings, M(y,r) usually produces the "right answer" on y, by definition of BPP. On PRG outputs, we just assumed that the majority of answers are wrong, because our vote got the answer wrong! So M(y,random) and M(y,PRG) will tend to disagree. This is a contradiction -- we assumed no efficient procedure could distinguish between PRG outputs and truly random strings. The above is a hasty sketch, that I hope gets a few of the ideas across. See Pseudorandom Generators: A Primer (http://www.wisdom.weizmann.ac.il/~oded/PDF/prg10.pdf) theorem 2.16. Anyway, if we had good enough lower bounds against procedures with advice (see other comments) we could produce such PRGs. |