2026-09-18T21:06:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25975 2026-09-05T19:31:53Z ddc:004 open_access

Nearly-Optimal Private Selection via Gaussian Mechanism Leeman, Ethan Manurangsi, Pasin Differentially Private Selection Gaussian Mechanism Steinke [2025] recently asked the following intriguing open question: Can we solve the differentially private selection problem with nearly-optimal error by only (adaptively) invoking Gaussian mechanism on low-sensitivity queries? We resolve this question positively. In particular, for a candidate set 𝒴, we achieve error guarantee of Õ(log |𝒴|), which is within a factor of (log log |𝒴|)^{O(1)} of the exponential mechanism [McSherry and Talwar, 2007]. This improves on Steinke’s mechanism which achieves an error of O(log^{3/2} |𝒴|). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ethan Leeman and Pasin Manurangsi 2026 Is Part Of LIPIcs, Volume 368, 7th Symposium on Foundations of Responsible Computing (FORC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FORC.2026.4 urn:nbn:de:0030-drops-259750 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2026.4 eng https://creativecommons.org/licenses/by/4.0/legalcode