Hardness as randomness: a survey of universal derandomization

Simple item page
dc.creatorImpagliazzo, Russell
dc.date2003-04-28
dc.date.accessioned2026-07-07T12:12:31Z
dc.date.available2026-07-07T12:12:31Z
dc.descriptionWe 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.
dc.identifierhttps://arxiv.org/abs/cs/0304040
dc.identifierhttp://arxiv.org/abs/cs/0304040
dc.identifierProceedings of the ICM, Beijing 2002, vol. 3, 659--672
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/210569
dc.subjectComputational Complexity
dc.subject68Q15, 68Q10, 68Q17, 68W20
dc.subjectF.1
dc.titleHardness as randomness: a survey of universal derandomization
dc.typetext

Files

Collections

arXiv