Hardness as randomness: a survey of universal derandomization

Abstract

We survey recent developments in the study of probabilistic complexity classes. While the evidence seems to support the conjecture that probabilism can be deterministically simulated with relatively low overhead, i.e., that $P=BPP$, it also indicates that this may be a difficult question to resolve. In fact, proving that probabilistic algorithms have non-trivial deterministic simulations is basically equivalent to proving circuit lower bounds, either in the algebraic or Boolean models.

Cited by in corpus (1)

• Quasi-Random Rumor Spreading: Reducing Randomness Can Be Costly