{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T13:12:26Z","timestamp":1778764346785,"version":"3.51.4"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"NSERC Discovery Grant","award":["RGPIN-2021-03206"],"award-info":[{"award-number":["RGPIN-2021-03206"]}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-20-CE23-0015"],"award-info":[{"award-number":["ANR-20-CE23-0015"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-PECY-0002"],"award-info":[{"award-number":["ANR-22-PECY-0002"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001804","name":"Canada Research Chairs","doi-asserted-by":"publisher","award":["CRC-2020-00004"],"award-info":[{"award-number":["CRC-2020-00004"]}],"id":[{"id":"10.13039\/501100001804","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,12]]},"abstract":"<jats:p>We revisit the task of releasing marginal queries under differential privacy with additive (correlated) Gaussian noise. We first give a construction for answering arbitrary workloads of weighted marginal queries, over arbitrary domains. Our technique is based on releasing queries in the Fourier basis with independent noise with carefully calibrated variances, and reconstructing the marginal query answers using the inverse Fourier transform. We show that our algorithm, which is a factorization mechanism, is exactly optimal among all factorization mechanisms, both for minimizing the sum of weighted noise variances, and for minimizing the maximum noise variance. Unlike algorithms based on optimizing over all factorization mechanisms via semidefinite programming, our mechanism runs in time polynomial in the dataset and the output size. This construction recovers results of Xiao et al. [Neurips 2023] with a simpler algorithm and optimality proof, and a better running time.<\/jats:p>\n                  <jats:p>\n                    We then extend our approach to a generalization of marginals which we refer to as product queries. We show that our algorithm is still exactly optimal for this more general class of queries. Finally, we show how to embed extended marginal queries, which allow using a threshold predicate on numerical attributes, into product queries. We show that our mechanism is\n                    <jats:italic toggle=\"yes\">almost<\/jats:italic>\n                    optimal among all factorization mechanisms for extended marginals, in the sense that it achieves the optimal (maximum or average) noise variance up to lower order terms.\n                  <\/jats:p>","DOI":"10.1145\/3801919","type":"journal-article","created":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:50:22Z","timestamp":1778763022000},"page":"1-23","source":"Crossref","is-referenced-by-count":0,"title":["Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9517-8466","authenticated-orcid":false,"given":"Christian Janos","family":"Lebeda","sequence":"first","affiliation":[{"name":"Inria, Idesp, Inserm, University of Montpellier, Montpellier, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3435-7502","authenticated-orcid":false,"given":"Aleksandar","family":"Nikolov","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-3454-3631","authenticated-orcid":false,"given":"Haohua","family":"Tang","sequence":"additional","affiliation":[{"name":"University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Harvard Data Science Review","volume":"2","author":"Abowd John M.","year":"2022","unstructured":"John M. Abowd, Robert Ashmead, Ryan Cumings-Menon, Simson L. Garfinkel, Micah Heineck, Christine Heiss, Robert Johns, Daniel Kifer, Philip Leclerc, Ashwin Machanavajjhala, Brett Moran, William Sexton, Matthew Spence, and Pavel Zhuravlev. 2022. The 2020 Census Disclosure Avoidance System TopDown Algorithm. Harvard Data Science Review, Vol. 2 (2022)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265569"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591877"},{"key":"e_1_2_1_4_1","volume-title":"Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning. In International Conference on Machine Learning, ICML 2023","volume":"5963","author":"Choquette-Choo Christopher A.","year":"2023","unstructured":"Christopher A. Choquette-Choo, Hugh Brendan McMahan, J. Keith Rush, and Abhradeep Guha Thakurta. 2023. Multi-Epoch Matrix Factorization Mechanisms for Private Machine Learning. In International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA (Proceedings of Machine Learning Research, Vol. 202), Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett (Eds.). PMLR, 5924-5963. https:\/\/proceedings.mlr.press\/v202\/choquette-choo23a.html"},{"key":"e_1_2_1_5_1","unstructured":"Matthew Dawson Badih Ghazi Pritish Kamath Kapil Kumar Ravi Kumar Bo Luan Pasin Manurangsi Nishanth Mundru Harikesh Nair Adam Sealfon and Shengyu Zhu. 2023. Optimizing Hierarchical Queries for the Attribution Reporting API. In AdKDD@KDD (CEUR Workshop Proceedings Vol. 3556). CEUR-WS.org."},{"key":"e_1_2_1_6_1","first-page":"202","article-title":"Revealing information while preserving privacy","author":"Dinur Irit","year":"2003","unstructured":"Irit Dinur and Kobbi Nissim. 2003. Revealing information while preserving privacy. In PODS. ACM, 202-210.","journal-title":"PODS. ACM"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12454"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9678-x"},{"key":"e_1_2_1_11_1","volume-title":"Santa Barbara","volume":"544","author":"Dwork Cynthia","year":"2004","unstructured":"Cynthia Dwork and Kobbi Nissim. 2004. Privacy-Preserving Datamining on Vertically Partitioned Databases. In Advances in Cryptology - CRYPTO 2004, 24th Annual International CryptologyConference, Santa Barbara, California, USA, August 15-19, 2004, Proceedings (Lecture Notes in Computer Science, Vol. 3152), Matthew K. Franklin (Ed.). Springer, 528-544."},{"key":"e_1_2_1_12_1","first-page":"425","article-title":"The power of factorization mechanisms in local and central differential privacy","author":"Edmonds Alexander","year":"2020","unstructured":"Alexander Edmonds, Aleksandar Nikolov, and Jonathan R. Ullman. 2020. The power of factorization mechanisms in local and central differential privacy. In STOC. ACM, 425-438.","journal-title":"STOC. ACM"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3287287"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"e_1_2_1_15_1","volume-title":"Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting. CoRR","author":"Henzinger Monika","year":"2025","unstructured":"Monika Henzinger, Nikita P. Kalinin, and Jalaj Upadhyay. 2025. Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting. CoRR, Vol. abs\/2509.14334 (2025)."},{"key":"e_1_2_1_16_1","volume-title":"Improved Differentially Private Continual Observation Using Group Algebra","author":"Henzinger Monika","unstructured":"Monika Henzinger and Jalaj Upadhyay. 2025. Improved Differentially Private Continual Observation Using Group Algebra. In SODA. SIAM, 2951-2970."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH183"},{"key":"e_1_2_1_18_1","unstructured":"JASON. 2020. Formal Privacy Methods for the 2020 Census. Technical Report JSR-19-2F. U.S. Census Bureau. https:\/\/www.census.gov\/programs-surveys\/decennial-census\/decade\/2020\/planning-management\/plan\/planning-docs\/privacy-methods-2020-census.html [Accessed 14-July-2025]."},{"key":"e_1_2_1_19_1","first-page":"775","volume-title":"Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010","author":"Kasiviswanathan Shiva Prasad","year":"2010","unstructured":"Shiva Prasad Kasiviswanathan, Mark Rudelson, Adam D. Smith, and Jonathan R. Ullman. 2010. 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 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, Leonard J. Schulman (Ed.). ACM, 775-784."},{"key":"e_1_2_1_20_1","unstructured":"Christian Janos Lebeda. 2023. Differentially Private Release of Sparse and Skewed Data. Ph.D. Dissertation. IT University of Copenhagen. https:\/\/en.itu.dk\/-\/media\/EN\/Research\/PhD-Programme\/PhD-defences\/2023\/PhD-thesis-Final-Version-Christian-Janos-Lebeda-pdf.pdf"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978315.9"},{"key":"e_1_2_1_22_1","first-page":"272","article-title":"Optimal error of query sets under the differentially-private matrix mechanism","author":"Li Chao","year":"2013","unstructured":"Chao Li and Gerome Miklau. 2013. Optimal error of query sets under the differentially-private matrix mechanism. In ICDT. ACM, 272-283.","journal-title":"ICDT. ACM"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0398-x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2406.02140"},{"key":"e_1_2_1_25_1","first-page":"751","article-title":"Factorization norms and hereditary discrepancy","volume":"2020","author":"Matou\u0161ek Ji\u0159\u00ed","year":"2020","unstructured":"Ji\u0159\u00ed Matou\u0161ek, Aleksandar Nikolov, and Kunal Talwar. 2020. Factorization norms and hereditary discrepancy. International Mathematics Research Notices, Vol. 2020, 3 (2020), 751-780.","journal-title":"International Mathematics Research Notices"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.791"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.778"},{"key":"e_1_2_1_28_1","volume-title":"ICML (Proceedings of Machine Learning Research","volume":"4444","author":"McKenna Ryan","year":"2019","unstructured":"Ryan McKenna, Daniel Sheldon, and Gerome Miklau. 2019. Graphical-model based estimation and inference for differential privacy. In ICML (Proceedings of Machine Learning Research, Vol. 97). PMLR, 4435-4444."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/130938943"},{"key":"e_1_2_1_30_1","first-page":"1","article-title":"General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. In ITCS (LIPIcs, Vol. 287)","volume":"85","author":"Nikolov Aleksandar","year":"2024","unstructured":"Aleksandar Nikolov and Haohua Tang. 2024. General Gaussian Noise Mechanisms and Their Optimality for Unbiased Mean Estimation. In ITCS (LIPIcs, Vol. 287). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 85:1-85:23.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2506.08201"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_68"},{"key":"e_1_2_1_33_1","volume-title":"Vadhan","author":"Ullman Jonathan R.","year":"2010","unstructured":"Jonathan R. Ullman and Salil P. Vadhan. 2010. PCPs and the Hardness of Generating Synthetic Data. Electron. Colloquium Comput. Complex., Vol. TR10-017 (2010). showeprint[ECCC]TR10-017 https:\/\/eccc.weizmann.ac.il\/report\/2010\/017"},{"key":"e_1_2_1_34_1","unstructured":"United States Census Bureau. 2021. The Census Bureau's Simulated Reconstruction-Abetted Re-identification Attack on the 2010 Census. https:\/\/www.census.gov\/data\/academy\/webinars\/2021\/disclosure-avoidance-series\/simulated-reconstruction-abetted-re-identification-attack-on-the-2010-census.html. [Accessed 14-July-2025]."},{"key":"e_1_2_1_35_1","volume-title":"ResidualPlanner: a scalable matrix mechanism for marginals and beyond. arXiv preprint arXiv:2305.08175","author":"Xiao Yingtai","year":"2025","unstructured":"Yingtai Xiao, Guanlin He, Levent Toksoz, Zeyu Ding, Danfeng Zhang, and Daniel Kifer. 2025. ResidualPlanner: a scalable matrix mechanism for marginals and beyond. arXiv preprint arXiv:2305.08175 (2025)."},{"key":"e_1_2_1_36_1","first-page":"20495","article-title":"An optimal and scalable matrix mechanism for noisy marginals under convex loss functions","volume":"36","author":"Xiao Yingtai","year":"2023","unstructured":"Yingtai Xiao, Guanlin He, Danfeng Zhang, and Daniel Kifer. 2023. An optimal and scalable matrix mechanism for noisy marginals under convex loss functions. Advances in Neural Information Processing Systems, Vol. 36 (2023), 20495-20539.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544871"},{"key":"e_1_2_1_38_1","volume-title":"PrivSyn: Differentially Private Data Synthesis. In USENIX Security Symposium. USENIX Association, 929-946","author":"Zhang Zhikun","year":"2021","unstructured":"Zhikun Zhang, Tianhao Wang, Ninghui Li, Jean Honorio, Michael Backes, Shibo He, Jiming Chen, and Yang Zhang. 2021. PrivSyn: Differentially Private Data Synthesis. In USENIX Security Symposium. USENIX Association, 929-946."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3801919","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T12:50:30Z","timestamp":1778763030000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3801919"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,12]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5,12]]}},"alternative-id":["10.1145\/3801919"],"URL":"https:\/\/doi.org\/10.1145\/3801919","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,12]]}}}