[METRIC 2011] Oded Goldreich

METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)
Workshop on Expanders and derandomization (March 21-25, 2011)
Mar 24, 13:30-14:30 - Oded Goldreich (Weizmann I., Rehovot)
In a World of P=BPP
----
We show that proving results such as BPP=P essentially necessitate the construction of suitable pseudorandom generators (i.e., generators that suffice for such derandomization results). In particular, the main incarnation of this equivalence refers to the standard notion of uniform derandomization and to the corresponding pseudorandom generators (i.e., the standard uniform notion of ``canonical derandomizers''). This equivalence bypasses the question of which hardness assumptions are required for establishing such derandomization results, which has received considerable attention in the last decade or so (starting with Impagliazzo and Wigderson [JCSS, 2001]).

We also identify a natural class of search problems that can be solved by deterministic polynomial-time reductions to BPP. This result is instrumental to the construction of the aforementioned pseudorandom generators (based on the assumption BPP=P), which is actually a reduction of the ``construction problem'' to BPP.