It is known $P=BPP$ is insufficient to derandomize $VV$ isolation lemma.

What does it mean to be 'insufficient' here? Is there some theorem which says $P=BPP$ $+$ 'condition $A$' gives derandomization of Valiant-Vazirani.

Of course $P=NP$ suffices as condition $A$. However I am looking for anything weaker that would be possible and if something weaker than $P=NP$ is not possible then why?

  • $\begingroup$ I think it mostly means that no one knows how to derandomize Valiant-Vazirani if you assume only that P=BPP. If you look at Klivans-van Melkebeek, you'll see that because the Nisan-Wigderson generator relativizes, one can derandomize Valiant-Vazirani assuming existence of a sufficiently hard function (enough for the relativized NW generator). So from a relativizing statement (NW generator) we get a conditional derand of V-V, but from P=BPP alone (which doesn't relativize) we don't know how to. $\endgroup$ – Joshua Grochow Feb 16 at 3:10
  • $\begingroup$ So, rather than "P=BPP + condition A" it's more like "condition A", which is known to imply P=BPP (but not conversely) also implies derand of V-V. $\endgroup$ – Joshua Grochow Feb 16 at 3:11
  • $\begingroup$ Something weaker than $P=NP$ and stronger than $P=BPP$? $\endgroup$ – T.... Feb 16 at 3:51
  • $\begingroup$ Existence of sufficiently hard functions for the (relativized) NW generator to work in this setting. I believe indeed that such functions imply P=BPP but don't imply P=NP. See Klivans-van Melkebeek for details. $\endgroup$ – Joshua Grochow Feb 16 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.