Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

On Pseudorandomness and Resource-Bounded Measure

Vikraman Arvind and Johannes Köbler


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