{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:36Z","timestamp":1781077536560,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384297","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"425-438","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["The power of factorization mechanisms in local and central differential privacy"],"prefix":"10.1145","author":[{"given":"Alexander","family":"Edmonds","sequence":"first","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandar","family":"Nikolov","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jonathan","family":"Ullman","sequence":"additional","affiliation":[{"name":"Northeastern University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"Apple Machine Learning Journal","author":"Privacy Team Apple Differential","year":"2017","unstructured":"Apple Differential Privacy Team . Learning with privacy at scale . Apple Machine Learning Journal , 2017 . Apple Differential Privacy Team. Learning with privacy at scale. Apple Machine Learning Journal, 2017."},{"key":"e_1_3_2_2_2_1","first-page":"2497","volume-title":"SODA","author":"Blasiok Jaroslaw","unstructured":"Jaroslaw Blasiok , Mark Bun , Aleksandar Nikolov , and Thomas Steinke . Towards instance-optimal private query release . In SODA , pages 2480\u2013 2497 . SIAM, 2019. Jaroslaw Blasiok, Mark Bun, Aleksandar Nikolov, and Thomas Steinke. Towards instance-optimal private query release. In SODA, pages 2480\u20132497. SIAM, 2019."},{"key":"e_1_3_2_2_3_1","first-page":"282","volume-title":"Proceedings of the 26th ACM Symposium on Principles of Database Systems, PODS \u201907","author":"Barak Boaz","unstructured":"Boaz Barak , Kamalika Chaudhuri , Cynthia Dwork , Satyen Kale , Frank McSherry , and Kunal Talwar . Privacy, accuracy , and consistency too: a holistic solution to contingency table release . In Proceedings of the 26th ACM Symposium on Principles of Database Systems, PODS \u201907 , pages 273\u2013 282 . ACM, 2007. Boaz Barak, Kamalika Chaudhuri, Cynthia Dwork, Satyen Kale, Frank McSherry, and Kunal Talwar. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In Proceedings of the 26th ACM Symposium on Principles of Database Systems, PODS \u201907, pages 273\u2013282. ACM, 2007."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214089"},{"key":"e_1_3_2_2_5_1","first-page":"459","volume-title":"Proceedings of the 26th Symposium on Operating Systems Principles, SOSP \u201917","author":"Bittau Andrea","unstructured":"Andrea Bittau , \u00dalfar Erlingsson , Petros Maniatis , Ilya Mironov , Ananth Raghunathan , David Lie , Mitch Rudominer , Ushasree Kode , Julien Tinnes , and Bernhard Seefeld . Prochlo : Strong privacy for analytics in the crowd . In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP \u201917 , pages 441\u2013 459 . ACM, 2017. Andrea Bittau, \u00dalfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinnes, and Bernhard Seefeld. Prochlo: Strong privacy for analytics in the crowd. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP \u201917, pages 441\u2013459. ACM, 2017."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195147"},{"key":"e_1_3_2_2_7_1","first-page":"447","volume-title":"Proceedings of the 37th ACM Symposium on Principles of Database Systems, PODS\u201918","author":"Bun Mark","unstructured":"Mark Bun , Jelani Nelson , and Uri Stemmer . Heavy hitters and the structure of local privacy . In Proceedings of the 37th ACM Symposium on Principles of Database Systems, PODS\u201918 , pages 435\u2013 447 . ACM, 2018. Mark Bun, Jelani Nelson, and Uri Stemmer. Heavy hitters and the structure of local privacy. In Proceedings of the 37th ACM Symposium on Principles of Database Systems, PODS\u201918, pages 435\u2013447. ACM, 2018."},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591877"},{"key":"e_1_3_2_2_9_1","volume-title":"Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):26","author":"Hubert Chan T-H","year":"2011","unstructured":"T-H Hubert Chan , Elaine Shi , and Dawn Song . Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):26 , 2011 . T-H Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3):26, 2011."},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554833"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2017.1389735"},{"key":"e_1_3_2_2_12_1","volume-title":"September 2017 meeting of the Census Scientific Advisory Committee.","author":"Dajani Aref N.","unstructured":"Aref N. Dajani , Amy D. Lauger , Phyllis E. Singer , Daniel Kifer , Jerome P. Reiter , Ashwin Machanavajjhala , Simson L. Garfinkel , Scot A. Dahl , Matthew Graham , Vishesh Karwa , Hang Kim , Philip Lelerc , Ian M. Schmutte , William N. Sexton , Lars Vilhuber , and John M. Abowd . The modernization of statistical disclosure limitation at the U.S. census bureau, 2017 . Presented at the September 2017 meeting of the Census Scientific Advisory Committee. Aref N. Dajani, Amy D. Lauger, Phyllis E. Singer, Daniel Kifer, Jerome P. Reiter, Ashwin Machanavajjhala, Simson L. Garfinkel, Scot A. Dahl, Matthew Graham, Vishesh Karwa, Hang Kim, Philip Lelerc, Ian M. Schmutte, William N. Sexton, Lars Vilhuber, and John M. Abowd. The modernization of statistical disclosure limitation at the U.S. census bureau, 2017. Presented at the September 2017 meeting of the Census Scientific Advisory Committee."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_2_14_1","first-page":"210","volume-title":"Proceedings of the 22nd ACM Symposium on Principles of Database Systems, PODS \u201903","author":"Dinur Irit","unstructured":"Irit Dinur and Kobbi Nissim . Revealing information while preserving privacy . In Proceedings of the 22nd ACM Symposium on Principles of Database Systems, PODS \u201903 , pages 202\u2013 210 . ACM, 2003. Irit Dinur and Kobbi Nissim. Revealing information while preserving privacy. In Proceedings of the 22nd ACM Symposium on Principles of Database Systems, PODS \u201903, pages 202\u2013210. ACM, 2003."},{"key":"e_1_3_2_2_15_1","first-page":"544","volume-title":"Annual International Cryptology Conference","author":"Dwork Cynthia","unstructured":"Cynthia Dwork and Kobbi Nissim . Privacy-preserving datamining on vertically partitioned databases . In Annual International Cryptology Conference , pages 528\u2013 544 . Springer, 2004. Cynthia Dwork and Kobbi Nissim. Privacy-preserving datamining on vertically partitioned databases. In Annual International Cryptology Conference, pages 528\u2013544. Springer, 2004."},{"key":"e_1_3_2_2_16_1","first-page":"724","volume-title":"Symposium on Theory of Computing (STOC)","author":"Dwork Cynthia","unstructured":"Cynthia Dwork , Moni Naor , Toniann Pitassi , and Guy N. Rothblum . Differential privacy under continual observation . In Symposium on Theory of Computing (STOC) , pages 715\u2013 724 . ACM, 2010. Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. In Symposium on Theory of Computing (STOC), pages 715\u2013724. ACM, 2010."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9678-x"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_2_2_19_1","volume-title":"Duchi and Feng Ruan. The right complexity measure in locally private estimation: It is not the fisher information. arXiv preprint arXiv:1806.05756","author":"John","year":"2018","unstructured":"John C. Duchi and Feng Ruan. The right complexity measure in locally private estimation: It is not the fisher information. arXiv preprint arXiv:1806.05756 , 2018 . John C. Duchi and Feng Ruan. 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_2_20_1","first-page":"222","volume-title":"PODS","author":"Evfimievski Alexandre V.","unstructured":"Alexandre V. Evfimievski , Johannes Gehrke , and Ramakrishnan Srikant . Limiting privacy breaches in privacy preserving data mining . In PODS , pages 211\u2013 222 . ACM, 2003. Alexandre V. Evfimievski, Johannes Gehrke, and Ramakrishnan Srikant. Limiting privacy breaches in privacy preserving data mining. In PODS, pages 211\u2013222. ACM, 2003."},{"key":"e_1_3_2_2_21_1","volume-title":"Proceedings of the 2014 ACM Conference on Computer and Communications Security, CCS\u201914","author":"Erlingsson \u00dalfar","year":"2014","unstructured":"\u00dalfar Erlingsson , Vasyl Pihur , and Aleksandra Korolova . RAPPOR : Randomized aggregatable privacy-preserving ordinal response . In Proceedings of the 2014 ACM Conference on Computer and Communications Security, CCS\u201914 . ACM, 2014 . \u00dalfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacy-preserving ordinal response. In Proceedings of the 2014 ACM Conference on Computer and Communications Security, CCS\u201914. ACM, 2014."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022905618164"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993742"},{"key":"e_1_3_2_2_24_1","volume-title":"R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques. Bol. Soc. Mat. S ao Paulo, 8:1\u201379","author":"Grothendieck A.","year":"1953","unstructured":"A. Grothendieck . R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques. Bol. Soc. Mat. S ao Paulo, 8:1\u201379 , 1953 . A. Grothendieck. R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques. Bol. Soc. Mat. S ao Paulo, 8:1\u201379, 1953."},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.15"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3187009.3177733"},{"key":"e_1_3_2_2_28_1","first-page":"401","volume-title":"STOC","author":"Kearns Michael J.","unstructured":"Michael J. Kearns . Efficient noise-tolerant learning from statistical queries . In STOC , pages 392\u2013 401 . ACM, May 16-18 1993. Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. In STOC, pages 392\u2013401. ACM, May 16-18 1993."},{"key":"e_1_3_2_2_29_1","first-page":"540","volume-title":"FOCS","author":"Kasiviswanathan Shiva Prasad","unstructured":"Shiva Prasad Kasiviswanathan , Homin K. Lee , Kobbi Nissim , Sofya Raskhodnikova , and Adam Smith . What can we learn privately ? In FOCS , pages 531\u2013 540 . IEEE, Oct 25\u201328 2008. Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? In FOCS, pages 531\u2013540. IEEE, Oct 25\u201328 2008."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.21398"},{"key":"e_1_3_2_2_31_1","first-page":"784","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC \u201910","author":"Kasiviswanathan Shiva Prasad","unstructured":"Shiva Prasad Kasiviswanathan , Mark Rudelson , Adam Smith , and Jonathan Ullman . The price of privately releasing contingency tables and the spectra of random matrices with correlated rows . In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC \u201910 , pages 775\u2013 784 . ACM, 2010. Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam Smith, and Jonathan Ullman. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC \u201910, pages 775\u2013784. ACM, 2010."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_3_2_2_33_1","first-page":"134","volume-title":"Proceedings of the 29th ACM Symposium on Principles of Database Systems, PODS\u201910","author":"Li Chao","unstructured":"Chao Li , Michael Hay , Vibhor Rastogi , Gerome Miklau , and Andrew McGregor . Optimizing linear counting queries under differential privacy . In Proceedings of the 29th ACM Symposium on Principles of Database Systems, PODS\u201910 , pages 123\u2013 134 . ACM, 2010. Chao Li, Michael Hay, Vibhor Rastogi, Gerome Miklau, and Andrew McGregor. Optimizing linear counting queries under differential privacy. In Proceedings of the 29th ACM Symposium on Principles of Database Systems, PODS\u201910, pages 123\u2013134. ACM, 2010."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2160-5"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1526612.1526614"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231769"},{"key":"e_1_3_2_2_38_1","first-page":"1021","volume-title":"42nd International Colloquium, ICALP","author":"Nikolov Aleksandar","year":"2015","unstructured":"Aleksandar Nikolov . An improved private mechanism for small databases. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP , pages 1010\u2013 1021 , 2015 . Aleksandar Nikolov. An improved private mechanism for small databases. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP, pages 1010\u20131021, 2015."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01263419"},{"key":"e_1_3_2_2_40_1","first-page":"336","volume-title":"Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201915","author":"Nikolov Aleksandar","unstructured":"Aleksandar Nikolov and Kunal Talwar . Approximating hereditary discrepancy via small width ellipsoids . In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201915 , pages 324\u2013 336 . SIAM, 2015. Aleksandar Nikolov and Kunal Talwar. Approximating hereditary discrepancy via small width ellipsoids. In Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201915, pages 324\u2013336. SIAM, 2015."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938943"},{"issue":"2","key":"e_1_3_2_2_42_1","first-page":"237","article-title":"Grothendieck\u2019s theorem, past and present. Bull. Amer. Math. Soc. (N.","volume":"49","author":"Pisier Gilles","year":"2012","unstructured":"Gilles Pisier . Grothendieck\u2019s theorem, past and present. Bull. Amer. Math. Soc. (N. S.) , 49 ( 2 ): 237 \u2013 323 , 2012 . Gilles Pisier. Grothendieck\u2019s theorem, past and present. Bull. Amer. Math. Soc. (N.S.), 49(2):237\u2013323, 2012.","journal-title":"S.)"},{"key":"e_1_3_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_3_2_2_44_1","series-title":"Lecture Notes in Computer Science","first-page":"200","volume-title":"ALT","author":"Sz\u00f6r\u00e9nyi Bal\u00e1zs","unstructured":"Bal\u00e1zs Sz\u00f6r\u00e9nyi . Characterizing statistical query learning: Simplified notions and proofs . In ALT , volume 5809 of Lecture Notes in Computer Science , pages 186\u2013 200 . Springer, 2009. Bal\u00e1zs Sz\u00f6r\u00e9nyi. Characterizing statistical query learning: Simplified notions and proofs. In ALT, volume 5809 of Lecture Notes in Computer Science, pages 186\u2013200. Springer, 2009."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_68"},{"key":"e_1_3_2_2_46_1","volume-title":"William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. Differentially private sql with bounded user contribution. arXiv preprint arXiv:1909.01917","author":"Wilson Royce J","year":"2019","unstructured":"Royce J Wilson , Celia Yuxin Zhang , William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. Differentially private sql with bounded user contribution. arXiv preprint arXiv:1909.01917 , 2019 . Royce J Wilson, Celia Yuxin Zhang, William Lam, Damien Desfontaines, Daniel Simmons-Marengo, and Bryant Gipson. Differentially private sql with bounded user contribution. arXiv preprint arXiv:1909.01917, 2019."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384297","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384297"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":45,"alternative-id":["10.1145\/3357713.3384297","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384297","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}