2026-08-08T14:55:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19531 2024-03-06T11:04:14Z ddc:004 open_access

Differentially Private Medians and Interior Points for Non-Pathological Data Aliakbarpour, Maryam Silver, Rose Steinke, Thomas Ullman, Jonathan Differential Privacy Statistical Estimation Approximate Medians Interior Point Problem We construct sample-efficient differentially private estimators for the approximate-median and interior-point problems, that can be applied to arbitrary input distributions over ℝ satisfying very mild statistical assumptions. Our results stand in contrast to the surprising negative result of Bun et al. (FOCS 2015), which showed that private estimators with finite sample complexity cannot produce interior points on arbitrary distributions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maryam Aliakbarpour and Rose Silver and Thomas Steinke and Jonathan Ullman 2024 Is Part Of LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2024.3 urn:nbn:de:0030-drops-195313 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.3 eng https://creativecommons.org/licenses/by/4.0/legalcode