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 a bounded round Arthur-Merlin game has subexponential
size membership proofs for infinitely many input lengths unless the
polynomial-time hierarchy collapses. This provides the first strong
evidence that graph nonisomorphism has subexponential size proofs.

We set up a general framework for derandomization which encompasses more
than the traditional model of randomized computation. For a randomized
procedure to fit within this framework, we only require that for any fixed
input the complexity of checking whether the procedure succeeds on a given
random bit sequence is not too high. We then apply our derandomization
technique to four fundamental complexity theoretic constructions:

1. The Valiant-Vazirani random hashing technique which prunes the
number of satisfying assignments of a Boolean formula to one, and related
procedures like computing satisfying assignments to Boolean formulas
non-adaptively given access to an oracle for satisfiability.

2. The algorithm of Bshouty et al. for learning Boolean circuits.
3. Constructing matrices with high rigidity. 4. Constructing
polynomial-size universal traversal sequences.

We also show that if linear space requires exponential size circuits, then
space bounded randomized computations can be simulated deterministically
with only a constant factor overhead in space.