[POPL'26] Dependent Coeffects for Local Sensitivity Analysis скачать в хорошем качестве

[POPL'26] Dependent Coeffects for Local Sensitivity Analysis

Dependent Coeffects for Local Sensitivity Analysis (Video, POPL 2026) Victor Sannier, Patrick Baillot (Univ. Lille - CNRS - Inria - Centrale Lille - UMR 9189 CRIStAL, France; Univ. Lille - CNRS - Inria - Centrale Lille - UMR 9189 CRIStAL, France) Abstract: Differential privacy is a formal definition of privacy that bounds the maximum acceptable information leakage when a query is performed on sensitive data. To ensure this property, a key technique involves bounding the query’s sensitivity (how much input variations affect the output) and adding noise to the result according to this quantity. While prior work like the Fuzz type system focuses on global sensitivity, many useful queries have infinite global sensitivity, restricting the scope of such approaches. This limitation can be addressed by considering a more fine-grained measure: local sensitivity, which quantifies output change for inputs adjacent to a specific dataset. In this article, we introduce Local Fuzz, a type system with dependent coeffects designed to bound the local sensitivity of programs written in a simple functional language. We provide a denotational semantics for this system in the category of extended premetric spaces, leveraging the recently introduced construction of a dependently graded comonad. Finally, we illustrate how Local Fuzz can lead to better differential privacy guarantees than Fuzz, both for mechanisms that rely on global sensitivity and for those that leverage local sensitivity, such as the Propose-Test-Release framework. Article: https://doi.org/10.1145/3776670 ORCID: https://orcid.org/0009-0005-1851-4119, https://orcid.org/0009-0002-9364-1140 Video Tags: sensitivity analysis, local sensitivity, differential privacy, coeffect systems, graded coeffects, linear types, doi:10.1145/3776670, orcid:0009-0005-1851-4119, orcid:0009-0002-9364-1140 Presentation at the POPL 2026 conference, Jan 11-17, 2026, https://popl26.sigplan.org/ Sponsored by ACM SIGPLAN.