Corelab Seminar
2010-2011
Antonis Antonopoulos (NTUA)
Derandomization: Simulation of BPP under Uniform Assumptions
Abstract.
In this lecture we present the first derandomization result based on a uniform assumption, proved by R.Impagliazzo and A.Wigderson in 1998. They showed that if BPP is not equal to EXP, then every BPP algorithm can be simulated deterministically in subexponential time on infinitely many input sizes.
This implies a "gap" in the deterministic (average-case) complexities of problems in BPP: Either they are always subexponential, or they contain arbitrary large exponential functions.
We will construct a small pseudorandom set of strings using a "hard" function in EXP with
certain properties, and we'll use this construction to show that a possible circuit distinguishing the pseudorandom strings from truly random strings implies the existence of a similarly sized circuit which computes the hard function.