What are the typical configurations of a spin model (for example, Ising model, or Potts model) on a random regular (bipartite) graph ? We show that the answer to this question is related to tree recursions (belief propagation) and p->q operator matrix norms. Understanding the typical configurations allows us to show hardness of approximating the partition function for certain multispin models...