Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses

Traditional hardness versus randomness results focus on time-efficient randomized decision procedures. We generalize these trade-os to a much wider class of randomized processes. We work out various applications, most notably to derandomizing Arthur-Merlin games. We show that every language with a bounded round Arthur-Merlin game has subexponential size membership proofs for infinitely many input lengths unless exponential time coincides with the third level of the polynomial-time hierarchy (and hence the polynomial-time hierarchy collapses). Since the graph nonisomorphism problem has a bounded round Arthur-Merlin game, this provides the first strong evidence that graph nonisomorphism has subexponential size proofs. We also establish hardness versus randomness trade-offs for space bounded computation.