{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:43:41Z","timestamp":1768110221992,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T00:00:00Z","timestamp":1733702400000},"content-version":"vor","delay-in-days":7,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["2128519, 2044679, 2338772, and 2148359"],"award-info":[{"award-number":["2128519, 2044679, 2338772, and 2148359"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Cisco","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Packard Fellowship"},{"name":"ONR"},{"name":"Intel"},{"DOI":"10.13039\/501100006374","name":"Bosch","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"name":"HKRGC","award":["16205420, 16205422, and 16204223"],"award-info":[{"award-number":["16205420, 16205422, and 16204223"]}]},{"DOI":"10.13039\/501100006374","name":"SRI","doi-asserted-by":"publisher","award":["DARPA SIEVE program"],"award-info":[{"award-number":["DARPA SIEVE program"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,12,2]]},"DOI":"10.1145\/3658644.3690225","type":"proceedings-article","created":{"date-parts":[[2024,12,9]],"date-time":"2024-12-09T12:19:20Z","timestamp":1733746760000},"page":"1939-1953","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Almost Instance-optimal Clipping for Summation Problems in the Shuffle Model of Differential Privacy"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0394-4125","authenticated-orcid":false,"given":"Wei","family":"Dong","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4167-8670","authenticated-orcid":false,"given":"Qiyao","family":"Luo","sequence":"additional","affiliation":[{"name":"OceanBase, Ant Group, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7671-2624","authenticated-orcid":false,"given":"Giulia","family":"Fanti","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5605-1048","authenticated-orcid":false,"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978318"},{"key":"e_1_3_2_1_2_1","first-page":"31","article-title":"Communication-efficient and differentially-private distributed sgd","author":"Agarwal N.","year":"2018","unstructured":"Agarwal, N., Suresh, A. T., Yu, F. X. X., Kumar, S., and McMahan, B. cpsgd: Communication-efficient and differentially-private distributed sgd. Advances in Neural Information Processing Systems 31 (2018).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_3_1","series-title":"SIAM Journal on computing 39, 1","volume-title":"The fast johnson--lindenstrauss transform and approximate nearest neighbors","author":"Ailon N.","year":"2009","unstructured":"Ailon, N., and Chazelle, B. The fast johnson--lindenstrauss transform and approximate nearest neighbors. SIAM Journal on computing 39, 1 (2009), 302--322."},{"key":"e_1_3_2_1_4_1","first-page":"17455","article-title":"Differentially private learning with adaptive clipping","volume":"34","author":"Andrew G.","year":"2021","unstructured":"Andrew, G., Thakkar, O., McMahan, B., and Ramaswamy, S. Differentially private learning with adaptive clipping. Advances in Neural Information Processing Systems 34 (2021), 17455--17466.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_5_1","volume-title":"Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems 33","author":"Asi H.","year":"2020","unstructured":"Asi, H., and Duchi, J. C. Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms. Advances in neural information processing systems 33 (2020)."},{"key":"e_1_3_2_1_6_1","first-page":"638","volume-title":"Proceedings, Part II 39","author":"Balle B.","year":"2019","unstructured":"Balle, B., Bell, J., Gasc\u00f3n, A., and Nissim, K. The privacy blanket of the shuffle model. In Advances in Cryptology--CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18--22, 2019, Proceedings, Part II 39 (2019), Springer, pp. 638--667."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3417242"},{"key":"e_1_3_2_1_8_1","first-page":"464","volume-title":"Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science","author":"Bassily R.","year":"2014","unstructured":"Bassily, R., Smith, A., and Thakurta, A. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium on foundations of computer science (2014), IEEE, pp. 464--473."},{"key":"e_1_3_2_1_9_1","first-page":"33","article-title":"Coinpress: Practical private mean and covariance estimation","author":"Biswas S.","year":"2020","unstructured":"Biswas, S., Dong, Y., Kamath, G., and Ullman, J. Coinpress: Practical private mean and covariance estimation. Advances in Neural Information Processing Systems 33 (2020).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132769"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133956.3133982"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17653-2_13"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49896-5_15"},{"key":"e_1_3_2_1_14_1","volume-title":"Subset-based instance optimality in private estimation. arXiv preprint arXiv:2303.01262","author":"Dick T.","year":"2023","unstructured":"Dick, T., Kulesza, A., Sun, Z., and Suresh, A. T. Subset-based instance optimality in private estimation. arXiv preprint arXiv:2303.01262 (2023)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_3_2_1_16_1","volume-title":"Almost instance-optimal clipping for summation problems in the shuffle model of differential privacy. arXiv preprint arXiv:2403.10116","author":"Dong W.","year":"2024","unstructured":"Dong,W., Luo, Q., Fanti, G., Shi, E., and Yi, K. Almost instance-optimal clipping for summation problems in the shuffle model of differential privacy. arXiv preprint arXiv:2403.10116 (2024)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589268"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588669"},{"key":"e_1_3_2_1_19_1","first-page":"3","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork C.","year":"2014","unstructured":"Dwork, C., and Roth, A. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science 9, 3--4 (2014), 211--407.","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310586"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560567"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77883-5_16"},{"key":"e_1_3_2_1_23_1","first-page":"3505","volume-title":"International Conference on Machine Learning","author":"Ghazi B.","year":"2020","unstructured":"Ghazi, B., Kumar, R., Manurangsi, P., and Pagh, R. Private counting from anonymous messages: Near-optimal accuracy with vanishing communication overhead. In International Conference on Machine Learning (2020), PMLR, pp. 3505--3514."},{"key":"e_1_3_2_1_24_1","first-page":"3692","volume-title":"International Conference on Machine Learning","author":"Ghazi B.","year":"2021","unstructured":"Ghazi, B., Kumar, R., Manurangsi, P., Pagh, R., and Sinha, A. Differentially private aggregation in the shuffle model: Almost central accuracy in almost a single message. In International Conference on Machine Learning (2021), PMLR, pp. 3692--3701."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_27"},{"key":"e_1_3_2_1_26_1","volume-title":"Scalable and differentially private distributed aggregation in the shuffled model. arXiv preprint arXiv:1906.08320","author":"Ghazi B.","year":"2019","unstructured":"Ghazi, B., Pagh, R., and Velingker, A. Scalable and differentially private distributed aggregation in the shuffled model. arXiv preprint arXiv:1906.08320 (2019)."},{"key":"e_1_3_2_1_27_1","volume-title":"Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems","author":"Huang Z.","year":"2021","unstructured":"Huang, Z., Liang, Y., and Yi, K. Instance-optimal mean estimation under differential privacy. Advances in Neural Information Processing Systems (2021)."},{"key":"e_1_3_2_1_28_1","volume-title":"San francisco city employee salary data. https:\/\/www.kaggle.com\/ datasets\/kaggle\/sf-salaries\/data","author":"Kaggle","year":"2014","unstructured":"Kaggle. San francisco city employee salary data. https:\/\/www.kaggle.com\/ datasets\/kaggle\/sf-salaries\/data, 2014."},{"key":"e_1_3_2_1_29_1","volume-title":"Japans 100 million customs trade statistics since","author":"Kaggle","year":"1988","unstructured":"Kaggle. Japans 100 million customs trade statistics since 1988. https:\/\/www. kaggle.com\/datasets\/zanjibar\/100-million-data-csv, 2020."},{"key":"e_1_3_2_1_30_1","volume-title":"Mnist - digit recognizer dataset. https:\/\/www.kaggle.com\/c\/digitrecognizer\/ data","author":"Kaggle","year":"2020","unstructured":"Kaggle. Mnist - digit recognizer dataset. https:\/\/www.kaggle.com\/c\/digitrecognizer\/ data, 2020."},{"key":"e_1_3_2_1_31_1","volume-title":"Monthly salary of public worker in brazil. https:\/\/www.kaggle.com\/ datasets\/gustavomodelli\/monthly-salary-of-public-worker-in-brazil","author":"Kaggle","year":"2020","unstructured":"Kaggle. Monthly salary of public worker in brazil. https:\/\/www.kaggle.com\/ datasets\/gustavomodelli\/monthly-salary-of-public-worker-in-brazil, 2020."},{"key":"e_1_3_2_1_32_1","volume-title":"Ontario public sector salary","author":"Kaggle","year":"2019","unstructured":"Kaggle. Ontario public sector salary 2019. https:\/\/www.kaggle.com\/datasets\/ rajacsp\/ontario, 2020."},{"key":"e_1_3_2_1_33_1","first-page":"1853","volume-title":"Conference on Learning Theory","author":"Kamath G.","year":"2019","unstructured":"Kamath, G., Li, J., Singhal, V., and Ullman, J. Privately learning highdimensional distributions. In Conference on Learning Theory (2019), PMLR, pp. 1853--1902."},{"key":"e_1_3_2_1_34_1","first-page":"2204","volume-title":"Conference on Learning Theory","author":"Kamath G.","year":"2020","unstructured":"Kamath, G., Singhal, V., and Ullman, J. Private mean estimation of heavy-tailed distributions. In Conference on Learning Theory (2020), PMLR, pp. 2204--2235."},{"key":"e_1_3_2_1_35_1","volume-title":"A primer on private statistics. arXiv preprint arXiv:2005.00010","author":"Kamath G.","year":"2020","unstructured":"Kamath, G., and Ullman, J. A primer on private statistics. arXiv preprint arXiv:2005.00010 (2020)."},{"key":"e_1_3_2_1_36_1","volume-title":"Learning differentially private recurrent language models. arXiv preprint arXiv:1710.06963","author":"McMahan H. B.","year":"2017","unstructured":"McMahan, H. B., Ramage, D., Talwar, K., and Zhang, L. Learning differentially private recurrent language models. arXiv preprint arXiv:1710.06963 (2017)."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146847.1146848"},{"key":"e_1_3_2_1_39_1","volume-title":"Adaclip: Adaptive clipping for private sgd. arXiv preprint arXiv:1908.07643","author":"Pichapati V.","year":"2019","unstructured":"Pichapati, V., Suresh, A. T., Yu, F. X., Reddi, S. J., and Kumar, S. Adaclip: Adaptive clipping for private sgd. arXiv preprint arXiv:1908.07643 (2019)."},{"key":"e_1_3_2_1_40_1","volume-title":"Expedia ceos total compensation pegged at 296 million for","author":"Schaal D.","year":"2021","unstructured":"Schaal, D. Expedia ceos total compensation pegged at 296 million for 2021. https:\/\/skift.com\/blog\/expedia-ceos-total-compensation-pegged-at-296-million-for-2021, 2022."},{"key":"e_1_3_2_1_41_1","first-page":"245","volume-title":"Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing","author":"Song S.","year":"2013","unstructured":"Song, S., Chaudhuri, K., and Sarwate, A. D. Stochastic gradient descent with differentially private updates. In 2013 IEEE global conference on signal and information processing (2013), IEEE, pp. 245--248."},{"key":"e_1_3_2_1_42_1","first-page":"1","article-title":"Locally private k-means clustering","volume":"22","author":"Stemmer U","year":"2021","unstructured":"Stemmer, U. Locally private k-means clustering. The Journal of Machine Learning Research 22, 1 (2021), 7964--7993.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_3_2_1_43_1","first-page":"31","article-title":"Differentially private k-means with constant multiplicative error","author":"Stemmer U.","year":"2018","unstructured":"Stemmer, U., and Kaplan, H. Differentially private k-means with constant multiplicative error. Advances in Neural Information Processing Systems 31 (2018).","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57048-8_7"}],"event":{"name":"CCS '24: ACM SIGSAC Conference on Computer and Communications Security","location":"Salt Lake City UT USA","acronym":"CCS '24","sponsor":["SIGSAC ACM Special Interest Group on Security, Audit, and Control"]},"container-title":["Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658644.3690225","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658644.3690225","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3658644.3690225","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T06:08:59Z","timestamp":1755842939000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3658644.3690225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"references-count":45,"alternative-id":["10.1145\/3658644.3690225","10.1145\/3658644"],"URL":"https:\/\/doi.org\/10.1145\/3658644.3690225","relation":{},"subject":[],"published":{"date-parts":[[2024,12,2]]},"assertion":[{"value":"2024-12-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}