We establish hardness versus randomness trade-offs for a
broad class of randomized procedures. In particular, we create efficient
nondeterministic simulations of bounded round Arthur-Merlin games using
a language in exponential time that cannot be decided by polynomial
size oracle circuits with access to satisfiability. We show that every
language with ... more >>>