{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:29Z","timestamp":1750220429502,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,10,10]],"date-time":"2022-10-10T00:00:00Z","timestamp":1665360000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            We prove a general connection between the\n            <jats:italic>communication<\/jats:italic>\n            complexity of two-player games and the\n            <jats:italic>sample<\/jats:italic>\n            complexity of their multi-player locally private analogues. We use this connection to prove sample complexity lower bounds for locally differentially private protocols as straightforward corollaries of results from communication complexity. In particular, we (1) use a communication lower bound for the hidden layers problem to prove an exponential sample complexity separation between sequentially and fully interactive locally private protocols, and (2) use a communication lower bound for the pointer chasing problem to prove an exponential sample complexity separation between\n            <jats:italic>k<\/jats:italic>\n            -round and (\n            <jats:italic>k+1<\/jats:italic>\n            )-round sequentially interactive locally private protocols, for every\n            <jats:italic>k<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/3459095","type":"journal-article","created":{"date-parts":[[2022,2,8]],"date-time":"2022-02-08T22:18:47Z","timestamp":1644358727000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Exponential Separations in Local Privacy"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2433-5270","authenticated-orcid":false,"given":"Matthew","family":"Joseph","sequence":"first","affiliation":[{"name":"Google Research New York, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jieming","family":"Mao","sequence":"additional","affiliation":[{"name":"Google Research New York, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aaron","family":"Roth","sequence":"additional","affiliation":[{"name":"Computer and Information Sciences Department, University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,10,10]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"The Challenge of Scientific Reproducibility and Privacy Protection for Statistical Agencies","author":"Abowd John M.","year":"2016","unstructured":"John M. Abowd. 2016. The Challenge of Scientific Reproducibility and Privacy Protection for Statistical Agencies. Technical Report. Census Scientific Advisory Committee."},{"key":"e_1_3_3_3_2","first-page":"2067","volume-title":"Proceedings of Machine Learning Research (Proceedings of Machine Learning Research)","volume":"89","author":"Acharya Jayadev","year":"2019","unstructured":"Jayadev Acharya, Clement Canonne, Cody Freitag, and Himanshu Tyagi. 2019. Test without trust: Optimal locally private distribution testing. In Proceedings of Machine Learning Research (Proceedings of Machine Learning Research), Kamalika Chaudhuri and Masashi Sugiyama (Eds.). Vol. 89. PMLR, 2067\u20132076. http:\/\/proceedings.mlr.press\/v89\/acharya19b.html."},{"key":"e_1_3_3_4_2","volume-title":"Learning with Privacy at Scale","author":"Apple Differential Privacy Team","year":"2017","unstructured":"Differential Privacy Team Apple. 2017. Learning with Privacy at Scale. Technical Report. Apple."},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_25"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132769"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2013.6736498"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688087"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2353994"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196981"},{"key":"e_1_3_3_12_2","article-title":"Distributed differential privacy via mixnets","author":"Cheu Albert","year":"2018","unstructured":"Albert Cheu, Adam Smith, Jonathan Ullman, David Zeber, and Maxim Zhilyaev. 2018. Distributed differential privacy via mixnets. arXiv preprint arXiv:1808.01394 (2018).","journal-title":"arXiv preprint arXiv:1808.01394"},{"key":"e_1_3_3_13_2","article-title":"Learning without interaction requires separation","author":"Daniely Amit","year":"2018","unstructured":"Amit Daniely and Vitaly Feldman. 2018. Learning without interaction requires separation. arXiv preprint arXiv:1809.09165 (2018).","journal-title":"arXiv preprint arXiv:1809.09165"},{"key":"e_1_3_3_14_2","first-page":"3574","volume-title":"Advances in Neural Information Processing Systems","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. In Advances in Neural Information Processing Systems. 3574\u20133583."},{"key":"e_1_3_3_15_2","article-title":"Lower bounds for locally private estimation via communication complexity","author":"Duchi John","year":"2019","unstructured":"John Duchi and Ryan Rogers. 2019. Lower bounds for locally private estimation via communication complexity. arXiv preprint arXiv:1902.00582 (2019).","journal-title":"arXiv preprint arXiv:1902.00582"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"977","DOI":"10.1145\/2897518.2897535","volume-title":"STOC","author":"Ganor Anat","year":"2016","unstructured":"Anat Ganor, Gillat Kol, and Ran Raz. 2016. Exponential separation of communication and external information. In STOC. 977\u2013986."},{"key":"e_1_3_3_21_2","first-page":"429","volume-title":"IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Joseph Matthew","year":"2019","unstructured":"Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. 2019. The role of interactivity in local differential privacy. In IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 429\u2013438."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293351"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.14"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222016"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.556671"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.35"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_7"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459095","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3459095","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:02Z","timestamp":1750193222000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3459095"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,10]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3459095"],"URL":"https:\/\/doi.org\/10.1145\/3459095","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,10,10]]},"assertion":[{"value":"2020-01-09","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-29","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}