We introduce a 2-round stochastic constraint-satisfaction problem, and show that its approximation version is complete for (the promise version of) the complexity class $\mathsf{AM}$. This gives a `PCP characterization' of $\mathsf{AM}$ analogous to the PCP Theorem for $\mathsf{NP}$. Similar characterizations have been given for higher levels of the Polynomial Hierarchy, and for $\mathsf{PSPACE}$; however, we suggest that the result for $\mathsf{AM}$ might be of particular significance for attempts to derandomize this class.

To test this notion, we pose some `Randomized Optimization Hypotheses' related to our stochastic CSPs that (in light of our result) would imply collapse results for $\mathsf{AM}$. Unfortunately, the hypotheses appear over-strong, and we present evidence against them. In the process we show that, if some language in $\mathsf{NP}$ is hard-on-average against circuits of size $2^{\Omega(n)}$, then there exist hard-on-average optimization problems of a particularly elegant form.

All our proofs use a powerful form of PCPs known as Probabilistically Checkable Proofs of Proximity, and demonstrate their versatility. We also use known results on randomness-efficient soundness- and hardness-amplification. In particular, we make essential use of the Impagliazzo-Wigderson generator; our analysis relies on a recent Chernoff-type theorem for expander walks.