Hardness as randomness: a survey of universal derandomization
<|reference_start|>Hardness as randomness: a survey of universal derandomization: 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.<|reference_end|>
@article{impagliazzo2003hardness,
    title={Hardness as randomness: a survey of universal derandomization},
    author={Russell Impagliazzo},
    journal={Proceedings of the ICM, Beijing 2002, vol. 3, 659--672},
    year={2003},
    archivePrefix={arXiv},
    eprint={cs/0304040},
    primaryClass={cs.CC}
}