There has been a recent wave of interest in intermediate trust models for\ndifferential privacy that eliminate the need for a fully trusted central data\ncollector, but overcome the limitations of local differential privacy. This\ninterest has led to the introduction of the shuffle model (Cheu et al.,\nEUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private\nmodel (Dwork et al., ITCS 2010). The message of this line of work is that, for\na variety of low-dimensional problems -- such as counts, means, and histograms\n-- these intermediate models offer nearly as much power as central differential\nprivacy. However, there has been considerably less success using these models\nfor high-dimensional learning and estimation problems. In this work, we show\nthat, for a variety of high-dimensional learning and estimation problems, both\nthe shuffle model and the pan-private model inherently incur an exponential\nprice in sample complexity relative to the central model. For example, we show\nthat, private agnostic learning of parity functions over $d$ bits requires\n$\\Omega(2^{d/2})$ samples in these models, and privately selecting the most\ncommon attribute from a set of $d$ choices requires $\\Omega(d^{1/2})$ samples,\nboth of which are exponential separations from the central model. Our work\ngives the first non-trivial lower bounds for these problems for both the\npan-private model and the general multi-message shuffle model.\n