The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be efficiently solved without randomness. This result was achieved by showing one could start from the assumption that there are problems in E that do not have small circuits, and obtain a universal pseudorandom generator to fool BPP algorithms. I say universal, because from one hard function (family) you obtain a single PRG that fools all time-limited distinguishers. What if we reverse the quantifiers? Would it be any easier to show that for every BPP algorithm, there exists some efficient PRG to derandomize it? The above result of course implies it (the universal PRG is such a PRG), but it relies on the hard-to-prove assumption that E does not have small circuits. Would it be possible to have weaker assumptions to get BPP derandomization, through problem-dependent PRGs?This is somewhat like a uniform version of Adleman's BPP in P/poly theorem: assuming X, for every problem L in BPP, we can use X and L to construct a PRG that generates the superwitnesses for L.
Problem-Dependent Derandomization
cc.complexity theory;derandomization;pseudorandomness