Some results on derandomization.
[PostScript | 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.
-
Theory of Computing Systems. Special issue on the 20th Symposium on
Theoretical Aspects of Computer Science. 38(2)211-227, 2005.
-
20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), LNCS
2607:212-222.