{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:32:44Z","timestamp":1787340764158,"version":"build-2736575974"},"reference-count":65,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries and has been a focus of a long line of work. For a given set of $d$ linear queries $A$ over a database $x \\in \\mathbb{R}^N$, we seek to find the differentially private mechanism that has the minimum mean squared error relative to the true answer $Ax$. For pure differential privacy, Hart and Talwar and Bhaskara et al. give an $O(\\log^2 d)$ approximation to the optimal mechanism. Our first contribution is to give an $O(\\log^2 d)$ approximation guarantee for the case of $(\\varepsilon,\\delta)$-approximate differential privacy. Our mechanism adds carefully chosen correlated Gaussian noise to the answers and runs in time polynomial in $d$ and $N$. The mechanism is based on a recursive construction of a \u201csmall\u201d enclosing ellipsoid of the sensitivity polytope $AB_1^N$, where $B_1^N$ denotes the $N$-dimensional $\\ell_1$ ball. Optimality is established relative to the spectral lower bound, through a variant of the classical Bourgain--Tzafriri restricted invertibility theorem. We next consider this question in the case when the number of individuals $n=\\|x\\|_1$ in the database is smaller than the number of queries $d$. We call this the small database setting. Since the work of Blum, Ligett, and Roth [STOC '08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 609--618.] it has been known that such a restriction can allow for mechanisms with lower error. Our second main contribution is to give, for both pure and $(\\varepsilon,\\delta)$-privacy, differentially private mechanisms which have mean squared error within $\\mbox{polylog}(d,N)$ of the optimal for any $A$ and $n$. The approximation is achieved by first applying the mechanism without considering the size of the database and then projecting the answer to the convex hull of feasible answers space $nAB_1^N$, which is guaranteed to contain the true answer $Ax$. By applying techniques from statistical estimation, we show such mechanisms can achieve the claimed approximation. When applied to counting queries, i.e., $A$ with entries in $\\{0,1\\}$, our mechanism achieves $\\widetilde{O}(\\sqrt{n})$ average error for both pure and $(\\varepsilon,\\delta)$-privacy. $\\widetilde{O}$ hides polylogarithmic factors in all the parameters such as $d$, $n$, $N$, and $1\/\\delta$. Previously, such a bound was only known for $(\\varepsilon,\\delta)$-privacy. For pure privacy, this bound improves upon the $\\widetilde{O}(n^{\\frac{2}{3}})$ bound of Blum, Ligett, and Roth and matches the lower bound implied by I. Dinur and K. Nissim, Proceedings of the 22nd PODS, ACM, 2003, pp. 202--210 up to logarithmic factors. The third question we consider is the accuracy gap between the pure and approximate privacy notions. By applying tools from convex geometry, we make a connection between the hereditary discrepancy lower bound of S. Muthukrishnan and A. Nikolov, STOC '12: Proceedings of the 44th Symposium on Theory of Computing, 2012, pp. 1285--1292 for $(\\varepsilon,\\delta)$-privacy and the volume lower bound of Hardt and Talwar for pure privacy. We are able to show that the gap in error between the optimal mechanisms satisfying pure and $(\\varepsilon,\\delta)$-differential privacy is bounded by a factor of $O({polylog}(d,N))$. The connection between hereditary discrepancy and private mechanisms also enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix $A$.<\/jats:p>","DOI":"10.1137\/130938943","type":"journal-article","created":{"date-parts":[[2016,4,27]],"date-time":"2016-04-27T12:59:48Z","timestamp":1461761988000},"page":"575-616","source":"Crossref","is-referenced-by-count":16,"title":["The Geometry of Differential Privacy: The Small Database and Approximate Cases"],"prefix":"10.1137","volume":"45","author":[{"given":"Aleksandar","family":"Nikolov","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Li","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,4,27]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"P. Austrin, V. Guruswami, and J. H\\aastad,\n                      $(2+\\epsilon)$-SAT Is NP-Hard\n                      , ECCC, 2013.","DOI":"10.1109\/FOCS.2014.9"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/BF01582137"},{"key":"atypb4","first-page":"3","author":"Bansal N.","year":"2010","journal-title":"IEEE"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"B. Barak, K. Chaudhuri, C. Dwork, S. Kale, F. McSherry, and K. Talwar,\n                      Privacy, accuracy, and consistency too: A holistic solution to contingency table release\n                      , in Proceedings of ACM PODS L. Libkin, ed., 2007, pp. 273-282.","DOI":"10.1145\/1265530.1265569"},{"key":"atypb6","first-page":"1269","author":"Bhaskara A.","year":"2012","journal-title":"ACM"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1988-0928998-8"},{"key":"atypb8","first-page":"609","author":"Blum A.","year":"2008","journal-title":"ACM"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.13"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01425510"},{"key":"atypb11","first-page":"1405","author":"Beck J.","year":"1995","journal-title":"MA"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772174"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. Bun, J. Ullman, and S. Vadhan,\n                      Fingerprinting codes and the price of approximate differential privacy\n                      , in Proceedings of the 46th Annual ACM Symposium on Theory of Computing, 2014, pp. 1-10.","DOI":"10.1145\/2591796.2591877"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"B. Chazelle,\n                      The Discrepancy Method: Randomness and Complexity\n                      , Cambridge University Press, Cambridge, UK, 2000.","DOI":"10.1017\/CBO9780511626371"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824783"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"M. Charikar, A. Newman, and A. Nikolov,\n                      Tight hardness results for minimizing discrepancy\n                      , in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, 2011, pp. 1607-1614.","DOI":"10.1137\/1.9781611973082.124"},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"T.H. Hubert Chan, E. Shi, and D. Song,\n                      Private and continual release of statistics\n                      , in Proceedings of ICALP, 2010.","DOI":"10.1007\/978-3-642-14162-1_34"},{"key":"atypb18","first-page":"321","author":"De A.","year":"2012","journal-title":"New York"},{"key":"atypb19","first-page":"486","author":"Dwork C.","year":"2006","journal-title":"Springer"},{"key":"atypb21","first-page":"85","author":"Dwork C.","year":"2007","journal-title":"ACM"},{"key":"atypb22","first-page":"202","author":"Dinur I.","year":"2003","journal-title":"ACM"},{"key":"atypb23","first-page":"528","author":"Dwork C.","year":"2004","journal-title":"New York"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. Naor, O. Reingold, G. N. Rothblum, and S. Vadhan,\n                      On the complexity of differentially private data release: Efficient algorithms and hardness results\n                      , in STOC '09: Proceedings of the 41st Annual ACM symposium on Theory of Computing, 2009, pp. 381-390.","DOI":"10.1145\/1536414.1536467"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582123"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"C. Dwork, G. N. Rothblum, and S. Vadhan,\n                      Boosting and differential privacy\n                      , in Proceedings of FOCS '10: the IEEE 51st Annual Symposium on Foundations of Computer Science, 2010, pp. 51-60.","DOI":"10.1109\/FOCS.2010.12"},{"key":"atypb27","first-page":"217","author":"Ding B.","year":"2011","journal-title":"Proceedings of the SIGMOD Conference"},{"key":"atypb28","first-page":"469","author":"Dwork C.","year":"2008","journal-title":"Springer"},{"key":"atypb29","first-page":"445","author":"Fawaz N.","year":"2013","journal-title":"New York"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"atypb31","first-page":"803","author":"Gupta A.","year":"2011","journal-title":"Proceedings of STOC"},{"key":"atypb32","unstructured":"A. Giannopoulos,\n                      Notes on Isotropic Convex Bodies\n                      , http:\/\/users.uoa.gr\/ apgiannop\/notes.html (2003)."},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1070\/SM1989v064n01ABEH003295"},{"key":"atypb34","first-page":"351","author":"Ghosh A.","year":"2009","journal-title":"Proceedings of STOC"},{"key":"atypb35","first-page":"339","author":"Gupta A.","year":"2012","journal-title":"New York"},{"key":"atypb36","first-page":"135","author":"Gupte M.","year":"2010","journal-title":"ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems"},{"key":"atypb37","first-page":"155","author":"Guruswami V.","year":"2000","journal-title":"New York"},{"key":"atypb38","unstructured":"M. Hardt, K. Ligett, and F. McSherry, in NIPS (2012), pp. 2348-2356."},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"atypb40","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920970"},{"key":"atypb41","doi-asserted-by":"crossref","unstructured":"M. Hardt and K. Talwar,\n                      On the geometry of differential privacy\n                      , in STOC '10: Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, pp. 705-714.","DOI":"10.1145\/1806689.1806786"},{"key":"atypb42","unstructured":"F. John,\n                      Extremum problems with inequalities as subsidiary conditions\n                      , in Studies and Essays Presented to R. Courant on his 60th Birthday, 1948, pp. 187-204."},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1287\/moor.21.2.307"},{"key":"atypb44","doi-asserted-by":"crossref","unstructured":"S. Kasiviswanathan, M. Rudelson, and A. Smith,\n                      The power of linear reconstruction attacks\n                      , in Proceedings of 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, pp. 1415-1433.","DOI":"10.1137\/1.9781611973105.102"},{"key":"atypb45","doi-asserted-by":"crossref","unstructured":"S. P. Kasiviswanathan, M. Rudelson, A. Smith, and J. Ullman,\n                      The price of privately releasing contingency tables and the spectra of random matrices with correlated rows\n                      , in STOC '10: Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, pp. 775-784.","DOI":"10.1145\/1806689.1806795"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-005-2653-6"},{"key":"atypb47","doi-asserted-by":"crossref","unstructured":"C. Li, M. Hay, V. Rastogi, G. Miklau, and A. McGregor,\n                      Optimizing linear counting queries under differential privacy\n                      , in PODS '10: Proceedings of the 29th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2010, pp. 123-134.","DOI":"10.1145\/1807085.1807104"},{"key":"atypb48","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168653"},{"key":"atypb49","unstructured":"C. Li and G. Miklau,\n                      Measuring the Achievable Error of Query Sets Under Differential Privacy\n                      , CoRR: abs\/1202.3399, (2012)."},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(86)80041-5"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek,\n                      Geometric Discrepancy (An Illustrated Guide)\n                      , Springer, New York, 1999.","DOI":"10.1007\/978-3-642-03942-3"},{"key":"atypb52","unstructured":"J. Matou\u0161ek,\n                      The Determinant Bound for Discrepancy Is Almost Tight\n                      , arXiv:1101.0767, 2011."},{"key":"atypb53","doi-asserted-by":"crossref","unstructured":"S. Muthukrishnan and A. Nikolov,\n                      Optimal private halfspace counting via discrepancy\n                      , in STOC '12: Proceedings of the 44th Symposium on Theory of Computing, 2012, pp. 1285-1292.","DOI":"10.1145\/2213977.2214090"},{"key":"atypb54","doi-asserted-by":"crossref","unstructured":"K. Nissim, S. Raskhodnikova, and A. Smith,\n                      Smooth sensitivity and sampling in private data analysis\n                      , in STOC '07: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pp. 75-84.","DOI":"10.1145\/1250790.1250803"},{"key":"atypb55","doi-asserted-by":"crossref","unstructured":"A. Nikolov and K. Talwar,\n                      Approximating Hereditary Discrepancy via Small Width Ellipsoids\n                      , arXiv:1311.6204, 2013.","DOI":"10.1137\/1.9781611973730.24"},{"key":"atypb56","unstructured":"V. Rastogi, S. Hong, and D. Suciu,\n                      The boundary between privacy and utility in data publishing\n                      , in Proceedings of the 33rd International Conference on Very Large Databases, 2007, pp. 531-542."},{"key":"atypb57","doi-asserted-by":"crossref","unstructured":"A. Roth and T. Roughgarden,\n                      Interactive privacy via the median mechanism\n                      , in STOC '10: Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010, pp. 765-774","DOI":"10.1145\/1806689.1806794"},{"key":"atypb58","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2165799"},{"key":"atypb59","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer,\n                      The complexity of satisfiability problems\n                      , in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1978, pp. 216-226.","DOI":"10.1145\/800133.804350"},{"key":"atypb60","unstructured":"T. Tao,\n                      Topics in Random Matrix Theory\n                      , Grad. Stud. Math., 132, American Mathematical Society, Providence, RI, 2012."},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.02.013"},{"key":"atypb62","first-page":"361","author":"Ullman J.","year":"2013","journal-title":"Proceedings of STOC ("},{"key":"atypb63","doi-asserted-by":"publisher","DOI":"10.1007\/BF02809903"},{"key":"atypb64","first-page":"225","author":"Xiao X.","year":"2010","journal-title":"Proceedings of ICDE"},{"key":"atypb65","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15546-8_11"},{"key":"atypb66","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350252"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130938943","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:46:53Z","timestamp":1787338013000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130938943"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/130938943"],"URL":"https:\/\/doi.org\/10.1137\/130938943","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}