text: 423,69,1306934928765079554,1282679296843288577,Jonathan Ullman,"Really pleased with this new paper with my PhD student Albert Cheu. We prove strong lower bounds for two ""intermediate models"" of differential privacy: the shuffle model and the pan-private model. 1/3 <LINK> Our work builds in an essential way on Albert's awesome paper with Victor Balcer, @mgtjoseph, and Jieming Mao. 2/3 <LINK> It's awesome to have such a productive and independent PhD student! I can't believe he's graduating in the Spring. I'm jealous of whoever gets to be his next boss and/or post-doc advisor! *wink wink* 3/3",https://arxiv.org/abs/2009.08000,"There has been a recent wave of interest in intermediate trust models for differential privacy that eliminate the need for a fully trusted central data collector, but overcome the limitations of local differential privacy. This interest has led to the introduction of the shuffle model (Cheu et al., EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private model (Dwork et al., ITCS 2010). The message of this line of work is that, for a variety of low-dimensional problems -- such as counts, means, and histograms -- these intermediate models offer nearly as much power as central differential privacy. However, there has been considerably less success using these models for high-dimensional learning and estimation problems. In this work, we show that, for a variety of high-dimensional learning and estimation problems, both the shuffle model and the pan-private model inherently incur an exponential price in sample complexity relative to the central model. For example, we show that, private agnostic learning of parity functions over $d$ bits requires $\Omega(2^{d/2})$ samples in these models, and privately selecting the most common attribute from a set of $d$ choices requires $\Omega(d^{1/2})$ samples, both of which are exponential separations from the central model. Our work gives the first non-trivial lower bounds for these problems for both the pan-private model and the general multi-message shuffle model. ","The Limits of Pan Privacy and Shuffle Privacy for Learning and