Lijie Chen: The quest for superfast derandomization
Randomized algorithms are ubiquitous in computer science, but deterministic algorithms are preferable in many settings. Classic work in the theory of derandomization proved that every randomized algorithm can be derandomized convert into an equivalent deterministic algorithm) with at most a polynomial slowdown under plausible conjectures. However, the polynomial slowdown from classic work is huge, which renders it useless in practice. In this talk, I will survey recent developments which aim to obtain derandomization with as little overhead as possible. I will also explain a new framework that enables extremely fast derandomization.
|
|