 Authors: A. Klivans and D. van Melkebeek.
 Reference: SIAM Journal on Computing, 31: 15011526, 2002.
 Earlier versions:
Abstract
Traditional hardness versus randomness results focus on timeefficient
randomized decision procedures. We generalize these tradeoffs to a
much wider class of randomized processes. We work out various
applications, most notably to derandomizing ArthurMerlin games.
We show that every language with a bounded round ArthurMerlin game
has subexponential size membership proofs for infinitely many input
lengths unless exponential time coincides with the third level of
the polynomialtime hierarchy (and hence the polynomialtime hierarchy
collapses). Since the graph nonisomorphism problem has a bounded round
ArthurMerlin game, this provides the first strong evidence that
graph nonisomorphism has subexponential size proofs.
For a randomized procedure to fit within our 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
apply our derandomization technique to four other complexity
theoretic constructions:

The ValiantVazirani 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 nonadaptively given access to an oracle for
satisfiability.
 The algorithm of Bshouty et al. for learning Boolean
circuits.
 Constructing matrices with high rigidity.
 Constructing polynomialsize universal traversal sequences.
We also establish hardness versus randomness tradeoffs for space
bounded computation.