{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T18:20:14Z","timestamp":1771611614524,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":41,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T00:00:00Z","timestamp":1650844800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Science and Technology Commission of Shanghai Municipality Project Grant","award":["No. 19511120700"],"award-info":[{"award-number":["No. 19511120700"]}]},{"name":"National Natural Science Foundation of China Grant","award":["No. 61802069"],"award-info":[{"award-number":["No. 61802069"]}]},{"name":"Shanghai Science and Technology Commission Grant","award":["No. 17JC1420200"],"award-info":[{"award-number":["No. 17JC1420200"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,4,25]]},"DOI":"10.1145\/3485447.3512220","type":"proceedings-article","created":{"date-parts":[[2022,4,25]],"date-time":"2022-04-25T05:11:23Z","timestamp":1650863483000},"page":"599-609","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Compressive Sensing Approaches for Sparse Distribution Estimation Under Local Privacy"],"prefix":"10.1145","author":[{"given":"Zhongzheng","family":"Xiong","sequence":"first","affiliation":[{"name":"School of Data Science, Fudan University, China"}]},{"given":"Jialin","family":"Sun","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, China"}]},{"given":"Xiaojun","family":"Mao","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, Shanghai Jiao Tong University, China"}]},{"given":"Jian","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, China"}]},{"given":"Ying","family":"Shan","sequence":"additional","affiliation":[{"name":"Tencent, China"}]},{"given":"Zengfeng","family":"Huang","sequence":"additional","affiliation":[{"name":"School of Data Science, Fudan University, China"}]}],"member":"320","published-online":{"date-parts":[[2022,4,25]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Jayadev Acharya Peter Kairouz Yuhan Liu and Ziteng Sun. 2021. Estimating Sparse Discrete Distributions Under Privacy and Communication Constraints. In Algorithmic Learning Theory. PMLR 79\u201398."},{"key":"e_1_3_2_1_2_1","volume-title":"Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters. In International Conference on Machine Learning. 51\u201360","author":"Acharya Jayadev","year":"2019","unstructured":"Jayadev Acharya and Ziteng Sun. 2019. Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters. In International Conference on Machine Learning. 51\u201360."},{"key":"e_1_3_2_1_3_1","unstructured":"Jayadev Acharya Ziteng Sun and Huanyu Zhang. 2018. Hadamard response: Estimating distributions privately efficiently and with little communication. arXiv preprint arXiv:1802.04705(2018)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00365-007-9003-x"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2020.3039461"},{"key":"e_1_3_2_1_6_1","volume-title":"Linear Queries Estimation with Local Differential Privacy. In The 22nd International Conference on Artificial Intelligence and Statistics. 721\u2013729","author":"Bassily Raef","year":"2019","unstructured":"Raef Bassily. 2019. Linear Queries Estimation with Local Differential Privacy. In The 22nd International Conference on Artificial Intelligence and Statistics. 721\u2013729."},{"key":"e_1_3_2_1_7_1","unstructured":"Raef Bassily Kobbi Nissim Uri Stemmer and Abhradeep\u00a0Guha Thakurta. 2017. Practical locally private heavy hitters. In Advances in Neural Information Processing Systems. 2288\u20132296."},{"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\/3196959.3196981"},{"key":"e_1_3_2_1_10_1","volume-title":"Sparse representation of a polytope and recovery of sparse signals and low-rank matrices","author":"Cai T\u00a0Tony","year":"2013","unstructured":"T\u00a0Tony Cai and Anru Zhang. 2013. Sparse representation of a polytope and recovery of sparse signals and low-rank matrices. IEEE transactions on information theory 60, 1 (2013), 122\u2013132."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_3_2_1_12_1","volume-title":"Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 59, 8","author":"Candes J","year":"2006","unstructured":"Emmanuel\u00a0J Candes, Justin\u00a0K Romberg, and Terence Tao. 2006. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences 59, 8 (2006), 1207\u20131223."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.858979"},{"key":"e_1_3_2_1_14_1","unstructured":"Wei-Ning Chen Peter Kairouz and Ayfer \u00d6zg\u00fcr. 2020. Breaking the Communication-Privacy-Accuracy Trilemma. arXiv preprint arXiv:2007.11707(2020)."},{"key":"e_1_3_2_1_15_1","volume-title":"Advances in Neural Information Processing Systems. Curran Associates","author":"Ding Bolin","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting Telemetry Data Privately. In Advances in Neural Information Processing Systems. Curran Associates, Inc."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2011.2165289"},{"key":"e_1_3_2_1_18_1","volume-title":"Balls and bins: A study in negative dependence. BRICS Report Series 3, 25","author":"Dubhashi P","year":"1996","unstructured":"Devdatt\u00a0P Dubhashi and Desh Ranjan. 1996. Balls and bins: A study in negative dependence. BRICS Report Series 3, 25 (1996)."},{"key":"e_1_3_2_1_19_1","volume-title":"Conference on Learning Theory. PMLR, 1161\u20131191","author":"Duchi John","year":"2019","unstructured":"John Duchi and Ryan Rogers. 2019. Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory. PMLR, 1161\u20131191."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_3_2_1_21_1","volume-title":"Theory of cryptography conference","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 265\u2013284."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Aaron Roth 2014. The algorithmic foundations of differential privacy.Foundations and Trends in Theoretical Computer Science 9 3-4(2014) 211\u2013407.","DOI":"10.1561\/0400000042"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_3_2_1_24_1","unstructured":"Vitaly Feldman and Kunal Talwar. 2021. Lossless Compression of Efficient Private Local Randomizers. arXiv preprint arXiv:2102.12099(2021)."},{"key":"e_1_3_2_1_25_1","unstructured":"Peter Kairouz Keith Bonawitz and Daniel Ramage. 2016. Discrete distribution estimation under local privacy. arXiv preprint arXiv:1602.07387(2016)."},{"key":"e_1_3_2_1_26_1","unstructured":"Peter Kairouz Sewoong Oh and Pramod Viswanath. 2014. Extremal mechanisms for local differential privacy. In Advances in neural information processing systems. 2879\u20132887."},{"key":"e_1_3_2_1_27_1","volume-title":"Conference on Learning Theory. 1066\u20131100","author":"Kamath Sudeep","year":"2015","unstructured":"Sudeep Kamath, Alon Orlitsky, Dheeraj Pichapati, and Ananda\u00a0Theertha Suresh. 2015. On learning distributions from their samples. In Conference on Learning Theory. 1066\u20131100."},{"key":"e_1_3_2_1_28_1","first-page":"793","article-title":"What can we learn privately?SIAM J","volume":"40","author":"Kasiviswanathan Shiva\u00a0Prasad","year":"2011","unstructured":"Shiva\u00a0Prasad Kasiviswanathan, Homin\u00a0K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2011. What can we learn privately?SIAM J. Comput. 40, 3 (2011), 793\u2013826.","journal-title":"Comput."},{"key":"e_1_3_2_1_29_1","volume-title":"Theory of point estimation","author":"Lehmann L","unstructured":"Erich\u00a0L Lehmann and George Casella. 2006. Theory of point estimation. Springer Science & Business Media."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541788"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ALLERTON.2018.8635829"},{"key":"e_1_3_2_1_32_1","unstructured":"Ingo Roth Martin Kliesch Gerhard Wunder and Jens Eisert. 2016. Reliable recovery of hierarchically sparse signals and application in machine-type communications. arXiv preprint arXiv:1612.07806(2016)."},{"key":"e_1_3_2_1_33_1","unstructured":"Apple Differential\u00a0Privacy Team. 2017. Learning with privacy at scale. (2017)."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.834793"},{"key":"e_1_3_2_1_35_1","volume-title":"Negative association: definition, properties, and applications. Manuscript, available from https:\/\/goo. gl\/j2ekqM","author":"Wajc David","year":"2017","unstructured":"David Wajc. 2017. Negative association: definition, properties, and applications. Manuscript, available from https:\/\/goo. gl\/j2ekqM (2017)."},{"key":"e_1_3_2_1_36_1","volume-title":"International Conference on Machine Learning. PMLR, 6628\u20136637","author":"Wang Di","year":"2019","unstructured":"Di Wang and Jinhui Xu. 2019. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning. PMLR, 6628\u20136637."},{"key":"e_1_3_2_1_37_1","unstructured":"Shaowei Wang Liusheng Huang Pengzhan Wang Yiwen Nie Hongli Xu Wei Yang Xiang-Yang Li and Chunming Qiao. 2016. Mutual information optimally local private discrete distribution estimation. arXiv preprint arXiv:1607.08025(2016)."},{"key":"e_1_3_2_1_38_1","volume-title":"Locally Differentially Private Protocols for Frequency Estimation. In 26th USENIX Security Symposium (USENIX Security 17)","author":"Wang Tianhao","year":"2017","unstructured":"Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally Differentially Private Protocols for Frequency Estimation. In 26th USENIX Security Symposium (USENIX Security 17). USENIX Association."},{"key":"e_1_3_2_1_39_1","volume-title":"Locally differentially private heavy hitter identification","author":"Wang Tianhao","year":"2019","unstructured":"Tianhao Wang, Ninghui Li, and Somesh Jha. 2019. Locally differentially private heavy hitter identification. IEEE Transactions on Dependable and Secure Computing (2019)."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2809790"}],"event":{"name":"WWW '22: The ACM Web Conference 2022","location":"Virtual Event, Lyon France","acronym":"WWW '22","sponsor":["SIGWEB ACM Special Interest Group on Hypertext, Hypermedia, and Web"]},"container-title":["Proceedings of the ACM Web Conference 2022"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485447.3512220","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485447.3512220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:13Z","timestamp":1750188613000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485447.3512220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,25]]},"references-count":41,"alternative-id":["10.1145\/3485447.3512220","10.1145\/3485447"],"URL":"https:\/\/doi.org\/10.1145\/3485447.3512220","relation":{},"subject":[],"published":{"date-parts":[[2022,4,25]]},"assertion":[{"value":"2022-04-25","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}