Circuit Lower Bounds for Merlin–Arthur Classes

We show that for each $k>0$, MA/1 (MA with 1 bit of advice) does not have circuits of size nᵏ. 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)/1 which does not have circuits of size nᵏ. We also adapt our lower bound to the average-case setting; i.e., we show that MA/1 cannot be solved on more than 1/2+1/nᵏ fraction of inputs of length n by circuits of size nᵏ. Furthermore, we prove that MA does not have arithmetic circuits of size nᵏ for any k. As a corollary to our main result, we obtain that derandomization of MA/O(1) implies the existence of pseudorandom generators computable using $O(1)$ bits of advice.