{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,23]],"date-time":"2025-08-23T05:22:54Z","timestamp":1755926574203,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["1750640, 1816028, 1916020"],"award-info":[{"award-number":["1750640, 1816028, 1916020"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3450995","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1081-1094","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["The limits of pan privacy and shuffle privacy for learning and estimation"],"prefix":"10.1145","author":[{"given":"Albert","family":"Cheu","sequence":"first","affiliation":[{"name":"Northeastern University, USA"}]},{"given":"Jonathan","family":"Ullman","sequence":"additional","affiliation":[{"name":"Northeastern University, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"218","volume-title":"Pan-Private Uniformity Testing. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. 125","author":"Amin Kareem","year":"2020","unstructured":"Kareem Amin, Matthew Joseph, Jieming Mao, Jacob D. Abernethy, and Shivani Agarwal. 2020. Pan-Private Uniformity Testing. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. 125, PMLR. Pages 183\u2013218. arxiv:1911.01452"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITC.2020.1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.142"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_22"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417242"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64378-2_24"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_25"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132769"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188946"},{"key":"e_1_3_2_1_11_1","first-page":"167","volume-title":"Private Hypothesis Selection. In Advances in Neural Information Processing Systems. NeurIPS '19","author":"Bun Mark","year":"2019","unstructured":"Mark Bun, Gautam Kamath, Thomas Steinke, and Zhiwei Steven Wu. 2019. Private Hypothesis Selection. In Advances in Neural Information Processing Systems. NeurIPS '19. Pages 156\u2013167. arxiv:1905.13229"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591877"},{"key":"e_1_3_2_1_14_1","first-page":"288","volume-title":"Optimal Lower Bound for Differentially Private Multiparty Aggregation. In European Symposium on Algorithms. ESA '12","author":"Hubert Chan T.-H.","year":"2012","unstructured":"T.-H. Hubert Chan, Elaine Shi, and Dawn Song. 2012. Optimal Lower Bound for Differentially Private Multiparty Aggregation. In European Symposium on Algorithms. ESA '12. Pages 277\u2013288. https:\/\/eprint.iacr.org\/2012\/373"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.56"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_13"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773173"},{"key":"e_1_3_2_1_18_1","volume-title":"Gaussian differential privacy. arXiv preprint arXiv:1905.02383","author":"Dong Jinshuo","year":"2019","unstructured":"Jinshuo Dong, Aaron Roth, and Weijie J Su. 2019. Gaussian differential privacy. arXiv preprint arXiv:1905.02383, 2019. arxiv:1905.02383"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_3_2_1_20_1","first-page":"1191","volume-title":"Annual Conference on Learning Theory. COLT '19","author":"Duchi John","year":"2019","unstructured":"John Duchi and Ryan Rogers. 2019. Lower bounds for locally private estimation via communication complexity. In Annual Conference on Learning Theory. COLT '19. JMLR.org. Pages 1161\u20131191. arxiv:1902.00582"},{"key":"e_1_3_2_1_21_1","volume-title":"Duchi and Feng Ruan","author":"John","year":"2018","unstructured":"John C. Duchi and Feng Ruan. 2018. The Right Complexity Measure in Locally Private Estimation: It is not the Fisher Information. arXiv preprint arXiv:1806.05756, 2018."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_24_1","volume-title":"Pan-Private Streaming Algorithms. In Innovations in Computer Science. ICS '10","author":"Dwork Cynthia","year":"2010","unstructured":"Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N Rothblum, and Sergey Yekhanin. 2010. Pan-Private Streaming Algorithms. In Innovations in Computer Science. ICS '10. Tsinghua University Press. Pages 66\u201380."},{"key":"e_1_3_2_1_25_1","volume-title":"Concentrated differential privacy. arXiv preprint arXiv:1603.01887","author":"Dwork Cynthia","year":"2016","unstructured":"Cynthia Dwork and Guy N Rothblum. 2016. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016. arxiv:1603.01887"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-statistics-060116-054123"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.46"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384297"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.151"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITC.2020.15"},{"key":"e_1_3_2_1_31_1","volume-title":"On the Power of Multiple Anonymous Messages. In Foundations of Responsible Computing. FORC '20","author":"Ghazi Badih","year":"2020","unstructured":"Badih Ghazi, Noah Golowich, Ravi Kumar, Rasmus Pagh, and Ameya Velingker. 2020. On the Power of Multiple Anonymous Messages. In Foundations of Responsible Computing. FORC '20. arxiv:1908.11358"},{"key":"e_1_3_2_1_32_1","first-page":"3514","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Proceedings of Machine Learning Research. 119","author":"Ghazi Badih","year":"2020","unstructured":"Badih Ghazi, Ravi Kumar, Pasin Manurangsi, and Rasmus Pagh. 2020. Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. Proceedings of Machine Learning Research. 119, PMLR. Pages 3505\u20133514. http:\/\/proceedings.mlr.press\/v119\/ghazi20a.html"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_27"},{"key":"e_1_3_2_1_34_1","volume-title":"Scalable and Differentially Private Distributed Aggregation in the Shuffled Model. CoRR, abs\/1906.08320","author":"Ghazi Badih","year":"2019","unstructured":"Badih Ghazi, Rasmus Pagh, and Ameya Velingker. 2019. Scalable and Differentially Private Distributed Aggregation in the Shuffled Model. CoRR, abs\/1906.08320, 2019. arxiv:1906.08320"},{"key":"e_1_3_2_1_35_1","first-page":"1816","volume-title":"Locally Private Hypothesis Selection. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. 125","author":"Gopi Sivakanth","year":"2020","unstructured":"Sivakanth Gopi, Gautam Kamath, Janardhan Kulkarni, Aleksandar Nikolov, Zhiwei Steven Wu, Huanyu Zhang, Jacob D. Abernethy, and Shivani Agarwal. 2020. Locally Private Hypothesis Selection. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria]. Proceedings of Machine Learning Research. 125, PMLR. Pages 1785\u20131816. arxiv:2002.09465"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"e_1_3_2_1_37_1","volume-title":"Locally Private Gaussian Estimation. arXiv preprint arXiv:1811.08382","author":"Joseph Matthew","year":"2018","unstructured":"Matthew Joseph, Janardhan Kulkarni, Jieming Mao, and Zhiwei Steven Wu. 2018. Locally Private Gaussian Estimation. arXiv preprint arXiv:1811.08382, 2018."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00015"},{"key":"e_1_3_2_1_39_1","first-page":"1385","volume-title":"International Conference on Machine Learning. ICML '15","author":"Kairouz Peter","year":"2015","unstructured":"Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy. In International Conference on Machine Learning. ICML '15. PMLR. Pages 1376\u20131385. arxiv:1311.0776"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.27"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.14"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989290"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2017.11"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.57"},{"key":"e_1_3_2_1_47_1","volume-title":"Tight Bounds for Locally Differentially Private Selection. arXiv preprint arXiv:1802.02638","author":"Ullman Jonathan","year":"2018","unstructured":"Jonathan Ullman. 2018. Tight Bounds for Locally Differentially Private Selection. arXiv preprint arXiv:1802.02638, 2018."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3450995","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3450995","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3450995","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:43Z","timestamp":1750197703000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3450995"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":47,"alternative-id":["10.1145\/3406325.3450995","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3450995","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}