The consequences of the worst-case assumption NP=P are very well understood. On the other hand, we only know a few consequences of the average-case assumption ``NP is easy on average.'' In this paper we establish several new results on the worst-case complexity of Arthur-Merlin games (the class AM) under the average-case complexity assumption ``NP is easy on average.''

We first consider a stronger notion of ``NP is easy an average'' namely NP is easy on average with respect to distributions that are computable by a polynomial size circuit family. Under this assumption we show:

• AM &sube NSUBEXP.

Under the assumption that NP is easy on average with respect to polynomial-time computable distributions, we show:

• AME = E where AME is the exponential version of AM. This improves an earlier known result that if NP is easy on average then NE = E.
• For every c > 0, AM &sube [io-pseudo_NTIME(n^c)]-NP. Roughly this means that for any language L in AM there is a language L^' in NP so that it is computationally infeasible to distinguish L from L^'.

• Theory of Computing Systems, To appear.
• 15th International Symposium on Fundamentals of Computation Theory , LNCS 3623, 422-432 (2005).