Some results on derandomization.
[PDF]
Abstract
We show several results about derandomization including
- If NP is easy on average then efficient pseudorandom
generators exist and P=BPP.
- If NP is easy on average then given an NP machine M we
can easily on average find accepting computations of M(x) when it
accepts.
- For any A in EXP, if NEXPA is in PA/poly then
NEXPA=EXPA.
- If A is &Sigmak-complete and NEXPA is in PA/poly then
NEXPA=EXP=MAA.