On Pseudorandomness and Resource-Bounded Measure
Vikraman Arvind and Johannes Köbler
Abstract:
We extend a key result of Nisan and Wigderson to the nondeterministic setting. By applying this extension we are able to answer some questions left open by Lutz regarding the derandomization of the Sigma and Theta classes of the polynomial hierarchy under plausible measure theoretic assumptions. Further, by using the Nisan-Wigderson design of a pseudorandom generator, we unconditionally show that MA is a subclass of ZPP(NP) and that the intersection of MA and co-MA is low for ZPP(NP).
Ps-File: On Pseudorandomness and Resource-Bounded Measure