{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:17:20Z","timestamp":1778807840298,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T00:00:00Z","timestamp":1570147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Google Research Fellowship"},{"name":"Alfred P. Sloan Research Fellowship"},{"name":"DORECG","award":["N00014-17-1-2127"],"award-info":[{"award-number":["N00014-17-1-2127"]}]},{"name":"Google Faculty Research Award"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS-1447471 and 1565387"],"award-info":[{"award-number":["IIS-1447471 and 1565387"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"CAREER","award":["CCF-1350670"],"award-info":[{"award-number":["CCF-1350670"]}]},{"name":"ONR Young Investigator","award":["N00014-15-1-2388"],"award-info":[{"award-number":["N00014-15-1-2388"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,10,31]]},"abstract":"<jats:p>We present a new locally differentially private algorithm for the heavy hitters problem that achieves optimal worst-case error as a function of all standardly considered parameters. Prior work obtained error rates that depend optimally on the number of users, the size of the domain, and the privacy parameter but depend sub-optimally on the failure probability.<\/jats:p>\n          <jats:p>We strengthen existing lower bounds on the error to incorporate the failure probability and show that our new upper bound is tight with respect to this parameter as well. Our lower bound is based on a new understanding of the structure of locally private protocols. We further develop these ideas to obtain the following general results beyond heavy hitters.<\/jats:p>\n          <jats:p>\n            \u2022\n            <jats:italic>Advanced Grouposition<\/jats:italic>\n            : In the local model, group privacy for\n            <jats:italic>k<\/jats:italic>\n            users degrades proportionally to \u2248\u221a\n            <jats:italic>k<\/jats:italic>\n            instead of linearly in\n            <jats:italic>k<\/jats:italic>\n            as in the central model. Stronger group privacy yields improved max-information guarantees, as well as stronger lower bounds (via \u201cpacking arguments\u201d), over the central model.\n          <\/jats:p>\n          <jats:p>\u2022 Building on a transformation of Bassily and Smith\u00a0(STOC 2015), we give a generic transformation from any non-interactive approximate-private local protocol into a pure-private local protocol. Again in contrast with the central model, this shows that we cannot obtain more accurate algorithms by moving from pure to approximate local privacy.<\/jats:p>","DOI":"10.1145\/3344722","type":"journal-article","created":{"date-parts":[[2019,10,7]],"date-time":"2019-10-07T12:20:59Z","timestamp":1570450859000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Heavy Hitters and the Structure of Local Privacy"],"prefix":"10.1145","volume":"15","author":[{"given":"Mark","family":"Bun","sequence":"first","affiliation":[{"name":"Boston University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jelani","family":"Nelson","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Uri","family":"Stemmer","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Beer-Sheva, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,10,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"e_1_2_1_2_1","unstructured":"N. Alon and J. Spencer. 1992. The Probabilistic Method. John Wiley.  N. Alon and J. Spencer. 1992. The Probabilistic Method. John Wiley."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC\u201916)","author":"Bassily R."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Annual Conference on Advances in Neural Information Processing Systems (NIPS\u201917)","author":"Bassily R."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC\u201915)","author":"Bassily R."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 14th International Conference Theory of Cryptography (TCC\u201916-B). 635--658","author":"Bun M."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 20th Annual European Symposium on Algorithms (ESA\u201912)","author":"Chan T. H."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201913)","author":"Duchi J. C."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the Annual Conference on Advances in Neural Information Processing Systems (NIPS\u201915)","author":"Dwork C."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the ACM Symposium on the Theory of Computing (STOC\u201915)","author":"Dwork C."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Third Theory of Cryptography Conference. 265--284","author":"Dwork C."},{"key":"e_1_2_1_12_1","first-page":"3","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork C.","year":"2014","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS\u201910)","author":"Dwork C."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM Conference on Computer and Communications Security (CCS\u201914)","author":"Pihur V."},{"key":"e_1_2_1_15_1","first-page":"361","article-title":"Generalization of a probability limit theorem of cramer","volume":"54","author":"Feller W.","year":"1943","journal-title":"Trans. Am. Math. Soc."},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP\u201914)","author":"Gilbert A. C."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 2001 IEEE International Conference on Cluster Computing. 658--667","author":"Guruswami V."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 39th International Colloquium Automata, Languages, and Programming (ICALP\u201912)","author":"Hsu J."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Annual ACM Symposium on the Theory of Computing (STOC\u201911)","author":"Kane D. M."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Annual Conference on Neural Information Processing Systems 2018 (NeurIPS\u201918)","author":"Kaplan H."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_2_1_23_1","unstructured":"S. P. Kasiviswanathan and A. D. Smith. 2008. A note on differential privacy: Defining resistance to arbitrary side information. CoRR (2008) abs\/0803.3946.  S. P. Kasiviswanathan and A. D. Smith. 2008. A note on differential privacy: Defining resistance to arbitrary side information. CoRR (2008) abs\/0803.3946."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/12087222X"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Larsen K. G."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00252-1"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 25th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS\u201906)","author":"Mishra N."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press New York NY.  M. Mitzenmacher and E. Upfal. 2005. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press New York NY.","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Annual Converence on Algorithmic Learning Theory (ALT\u201918)","author":"Nissim K."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS\u201916)","author":"Qin Z."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201900)","author":"Reingold O."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Rogers R. M."},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Rogers R. M."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019223872X"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 2017 IEEE Symposium on Security and Privacy (SP\u201917)","author":"Smith A."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.556668"},{"key":"e_1_2_1_37_1","volume-title":"Locally private k-means clustering. CoRR","author":"Stemmer U.","year":"2019"},{"key":"e_1_2_1_38_1","unstructured":"A. Thakurta A. Vyrros U. Vaishampayan G. Kapoor J. Freudiger V. Sridhar and D. Davidson. 2017. Learning new words. US Patent 9594741 (2017).  A. Thakurta A. Vyrros U. Vaishampayan G. Kapoor J. Freudiger V. Sridhar and D. Davidson. 2017. Learning new words. US Patent 9594741 (2017)."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"S. Vadhan. 2016. The Complexity of Differential Privacy. https:\/\/privacytools.seas.harvard.edu\/publications\/complexity-differential-privacy.  S. Vadhan. 2016. The Complexity of Differential Privacy. https:\/\/privacytools.seas.harvard.edu\/publications\/complexity-differential-privacy.","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\/3344722","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3344722","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3344722","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:27Z","timestamp":1750204467000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3344722"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,4]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,10,31]]}},"alternative-id":["10.1145\/3344722"],"URL":"https:\/\/doi.org\/10.1145\/3344722","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,4]]},"assertion":[{"value":"2018-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-10-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}