{"ID":2843844,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06871","arxiv_id":"2511.06871","title":"Nearly-Optimal Private Selection via Gaussian Mechanism","abstract":"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 $\\mathcal{Y}$, we achieve error guarantee of $\\tilde{O}(\\log |\\mathcal{Y}|)$, which is within a factor of $(\\log \\log |\\mathcal{Y}|)^{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} |\\mathcal{Y}|)$.","short_abstract":"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 $\\mathcal{Y}$, we...","url_abs":"https://arxiv.org/abs/2511.06871","url_pdf":"https://arxiv.org/pdf/2511.06871v1","authors":"[\"Ethan Leeman\",\"Pasin Manurangsi\"]","published":"2025-11-10T09:17:33Z","proceeding":"cs.CR","tasks":"[\"cs.CR\",\"cs.DS\"]","methods":"[]","has_code":false}