Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-094 | 29th June 2023 21:46

New ways of studying the BPP = P conjecture


Authors: Lijie Chen, Roei Tell
Publication: 29th June 2023 22:21
Downloads: 2420


What's new in the world of derandomization? Questions about pseudorandomness and derandomization have been driving progress in complexity theory for many decades. In this survey we will describe new approaches to the $\mathcal{BPP}=\mathcal{P}$ conjecture from recent years, as well as new questions, algorithmic approaches, and ways of thinking. For example: Do we really need pseudorandom generators for derandomization, or can we get away with weaker objects? Can we prove free lunch theorems, eliminating randomness with zero computational overhead? What hardness assumptions are necessary and sufficient for derandomization? And how do new advances in this area interact with progress in cryptography and in interactive proof systems?

Note: A version of this text originally appeared as an ACM SIGACT News Complexity Theory Column.

ISSN 1433-8092 | Imprint