We show that for each k > 0, MA/1 (MA with 1 bit of advice) does not have circuits of size n^k. This implies the first superlinear circuit lower bounds for the promise versions of the classes MA, AM and ZPP_{||}^{NP}.

We extend our main result in several ways. For each k, we give an explicit language in (MA /cap coMA)/1 which doesn't have circuits of size n^k. We also adapt our lower bound to the average-case setting, i.e., we give languages L_{k} in MA/1 such that for infinitely many n, no circuit of size n^k solves L_{k} correctly on more than a 1/2+1/n^k fraction of inputs of length n. Furthermore, we prove that for any k, MA does not have arithmetic circuits of size n^k.

As a corollary to our main result, we obtain that derandomization of MA with O(1) bits of advice implies the existence of pseudo-random generators computable efficiently using O(1) bits of advice.