17

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.

Henry Yuen
  • 3,798
  • 1
  • 21
  • 33
  • 1
    I assume that by BPP, you mean the class of languages (instead of promise problems). Note that derandomizing an algorithm for a single PromiseBPP-complete problem is equivalent to derandomizing the whole PromiseBPP (using a single PRG). Therefore, if constructing “problem-dependent PRGs” is any easier than constructing a single PRG which works for all BPP algorithms, the technique must actively use the fact that you are considering languages instead of promise problems. I do not know how plausible this is. – Tsuyoshi Ito Oct 20 '11 at 11:44
  • What is an example of a PrBPP complete problem? How does derandomizing PrBPP differ from derandomizing BPP - are the required assumptions weaker? – Henry Yuen Oct 20 '11 at 15:06
  • An example of PromiseBPP-complete problems is a canonical one, that is, the BPP version of the bounded halting problem. As for the second question, I do not know. I do not see any reason why derandomizing BPP should be any easier than derandomizing PromiseBPP, and therefore I would be surprised if constructing a “problem-dependent PRG” for each language in BPP is any easier than the usual approach of constructing a single PRG which derandomizes the whole PromiseBPP, but who knows? – Tsuyoshi Ito Oct 20 '11 at 15:53
  • For derandomizing prBPP problems, a few papers of Goldreichs talk about doing what you are asking. See http://www.wisdom.weizmann.ac.il/~oded/p_bpp.html and the followup paper http://www.wisdom.weizmann.ac.il/~oded/p_targeted.html

    The conclusion of the second paper is that prBPP = P if and only if a certain kind of "targeted" derandomizer exists. By a result of Impagliazzo Kabanets (http://www.cs.sfu.ca/~kabanets/Research/poly.html) this implies that if these targeted derandomizers exist, then certain circuit lower bounds must also be proved.

     – Jeff KInne Jul 10 '12 at 02:36

0 Answers0