{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T12:23:40Z","timestamp":1779107020995,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":19,"publisher":"ACM","funder":[{"name":"Tel Aviv University","award":[""],"award-info":[{"award-number":[""]}]},{"name":"United States-Israel Binational Science Foundation","award":["2018385"],"award-info":[{"award-number":["2018385"]}]},{"name":"Technion-Israel Institute of Technology","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Blavatnik Family Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"name":"European Research Council","award":["101039692,882396"],"award-info":[{"award-number":["101039692,882396"]}]},{"name":"Israel Science Foundation","award":["1419\\\/24,1225\\\/20"],"award-info":[{"award-number":["1419\\\/24,1225\\\/20"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718274","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:21:27Z","timestamp":1750026087000},"page":"2362-2373","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["On Differentially Private Linear Algebra"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9586-8002","authenticated-orcid":false,"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"},{"name":"Google Research, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6891-2645","authenticated-orcid":false,"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"},{"name":"Google Research, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8662-2737","authenticated-orcid":false,"given":"Shay","family":"Moran","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"},{"name":"Google Research, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7584-8768","authenticated-orcid":false,"given":"Uri","family":"Stemmer","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"},{"name":"Google Research, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8810-4581","authenticated-orcid":false,"given":"Nitzan","family":"Tur","sequence":"additional","affiliation":[{"name":"Google Research, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"COLT (Proceedings of Machine Learning Research (PMLR)","volume":"152","author":"Alon Noga","year":"2020","unstructured":"Noga Alon, Amos Beimel, Shay Moran, and Uri Stemmer. 2020. Closure Properties for Private Classification and Online Prediction. In COLT (Proceedings of Machine Learning Research (PMLR), Vol. 125). 119\u2013152. http:\/\/proceedings.mlr.press\/v125\/alon20a.html"},{"key":"e_1_3_2_1_2_1","volume-title":"Conference on Learning Theory. 1075\u20131076","author":"Ashtiani Hassan","year":"2022","unstructured":"Hassan Ashtiani and Christopher Liaw. 2022. Private and polynomial time algorithms for learning Gaussians and beyond. In Conference on Learning Theory. 1075\u20131076."},{"key":"e_1_3_2_1_3_1","article-title":"Differential Privacy on Finite Computers","volume":"9","author":"Balcer Victor","year":"2019","unstructured":"Victor Balcer and Salil P. Vadhan. 2019. Differential Privacy on Finite Computers. J. Priv. Confidentiality, 9, 2 (2019).","journal-title":"J. Priv. Confidentiality"},{"key":"e_1_3_2_1_4_1","volume-title":"Private Center Points and Learning of Halfspaces. In Conference on Learning Theory, COLT 2019","volume":"282","author":"Beimel Amos","year":"2019","unstructured":"Amos Beimel, Shay Moran, Kobbi Nissim, and Uri Stemmer. 2019. Private Center Points and Learning of Halfspaces. In Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA, Alina Beygelzimer and Daniel Hsu (Eds.) (Proceedings of Machine Learning Research, Vol. 99). PMLR, 269\u2013282. http:\/\/proceedings.mlr.press\/v99\/beimel19a.html"},{"key":"e_1_3_2_1_5_1","unstructured":"Omri Ben-Eliezer Dan Mikulincer and Ilias Zadik. 2022. Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions. In NeurIPS."},{"key":"e_1_3_2_1_6_1","volume-title":"Vadhan","author":"Bun Mark","year":"2015","unstructured":"Mark Bun, Kobbi Nissim, Uri Stemmer, and Salil P. Vadhan. 2015. Differentially Private Release and Learning of Threshold Functions. In FOCS. 634\u2013649."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0095-7"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_3_2_1_9_1","volume-title":"Vadhan","author":"Dwork Cynthia","year":"2010","unstructured":"Cynthia Dwork, Guy N. Rothblum, and Salil P. Vadhan. 2010. Boosting and Differential Privacy. In FOCS. 51\u201360."},{"key":"e_1_3_2_1_10_1","first-page":"1","article-title":"Differentially Private Approximations of a Convex Hull in Low Dimensions. In ITC (LIPIcs, Vol. 199)","volume":"18","author":"Gao Yue","year":"2021","unstructured":"Yue Gao and Or Sheffet. 2021. Differentially Private Approximations of a Convex Hull in Low Dimensions. In ITC (LIPIcs, Vol. 199). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 18:1\u201318:16.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_11_1","volume-title":"Geometric algorithms and combinatorial optimization. 2","author":"Gr\u00f6tschel Martin","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. 2012. Geometric algorithms and combinatorial optimization. 2, Springer Science & Business Media."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"B. Gr\u00fcnbaum V. Kaibel V. Klee and G.M. Ziegler. 2003. Convex Polytopes. Springer. isbn:9780387404097 lccn:2003042435 https:\/\/books.google.co.il\/books?id=5iV75P9gIUgC","DOI":"10.1007\/978-1-4613-0019-9"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_51"},{"key":"e_1_3_2_1_14_1","volume-title":"Extremum problems with inequalities as subsidiary conditions, Studies and Essays Presented to R. Courant on his 60th Birthday","author":"John Fritz","unstructured":"Fritz John. 1948. Extremum problems with inequalities as subsidiary conditions, Studies and Essays Presented to R. Courant on his 60th Birthday."},{"key":"e_1_3_2_1_15_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems","author":"Kaplan Haim","year":"2020","unstructured":"Haim Kaplan, Yishay Mansour, Uri Stemmer, and Eliad Tsfadia. 2020. Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/a08e32d2f9a8b78894d964ec7fd4172e-Abstract.html"},{"key":"e_1_3_2_1_16_1","first-page":"1","article-title":"How to Find a Point in the Convex Hull Privately. In SoCG (LIPIcs, Vol. 164)","volume":"52","author":"Kaplan Haim","year":"2020","unstructured":"Haim Kaplan, Micha Sharir, and Uri Stemmer. 2020. How to Find a Point in the Convex Hull Privately. In SoCG (LIPIcs, Vol. 164). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 52:1\u201352:15.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_17_1","volume-title":"Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, Arindam Banerjee and Kenji Fukumizu (Eds.) (Proceedings of Machine Learning Research","volume":"2565","author":"Munoz Andres","year":"2021","unstructured":"Andres Munoz, Umar Syed, Sergei Vassilvtiskii, and Ellen Vitercik. 2021. Private optimization without constraint violations. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, Arindam Banerjee and Kenji Fukumizu (Eds.) (Proceedings of Machine Learning Research, Vol. 130). PMLR, 2557\u20132565. https:\/\/proceedings.mlr.press\/v130\/munoz21a.html"},{"key":"e_1_3_2_1_18_1","unstructured":"Vikrant Singhal and Thomas Steinke. 2021. Privately Learning Subspaces. In NeurIPS. 1312\u20131324."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2402.06465"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718274","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:47:44Z","timestamp":1750693664000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":19,"alternative-id":["10.1145\/3717823.3718274","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718274","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}