Interpreting the Error of Differentially Private Median Queries through Randomization Intervals

Computer Science > Cryptography and Security [Submitted on 8 Apr 2026] Interpreting the Error of Differentially Private Median Queries through Randomization Intervals Thomas Humphries, Tim Li, Shufan Zhang, Karl Knopf, Xi He It can be difficult for practitioners to interpret the quality of differentially private (DP) statistics due to the added noise. One method to help analysts understand the amount of error introduced by DP is to return a Randomization Interval (RI), along with the statistic. A RI is a type of confidence interval that bounds the error introduced by DP. For queries where the noise distribution depends on the input, such as the median, prior work degrades the quality of the median itself to obtain a high-quality RI. In this work, we propose PostRI, a solution to compute a RI after the median has been estimated. PostRI enables a median estimation with 14%-850% higher utility than related work, while maintaining a narrow RI. Comments: Presented at the 2026 TPDP workshop in Boston Subjects: Cryptography and Security (cs.CR); Databases (cs.DB) Cite as: arXiv:2604.07581 [cs.CR]   (or arXiv:2604.07581v1 [cs.CR] for this version)   https://doi.org/10.48550/arXiv.2604.07581 Focus to learn more Submission history From: Thomas Humphries [view email] [v1] Wed, 8 Apr 2026 20:35:41 UTC (1,411 KB) Access Paper: HTML (experimental) view license Current browse context: cs.CR < prev   |   next > new | recent | 2026-04 Change to browse by: cs cs.DB References & Citations NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)