Additive noise mechanisms for making randomized approximation algorithms differentially private

DOI10.4230/LIPICS.APPROX/RANDOM.2024.73MaRDI QIDQ6920763zbMATH OpenFDO

Authors Jakub Tětek

Publication date 6 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.73

zbMATH Keywords

differential privacyrandomized approximation algorithms

Mathematics Subject Classification ID

Randomized algorithms (68W20) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Cites work

• An improved constant-time approximation algorithm for maximum~matchings
• Differential Privacy
• Differentially private Continual releases of streaming frequency moment estimations
• Estimating the number of connected components in sublinear time
• Finding repeated elements
• High-dimensional probability. An introduction with applications in data science
• How to make your approximation algorithm private: a black-box differentially-private transformation for tunable approximation algorithms of functions with low sensitivity
• scientific article; zbMATH DE number 1256715 (Why is no real title available?)
• LogLog counting of large cardinalities (extended abstract)
• On approximating the number of k-cliques in sublinear time
• On the power of multiple anonymous messages: frequency estimation and selection in the shuffle model of differential privacy
• Optimal quantile approximation in streams
• Privately estimating graph parameters in sublinear time
• Quantitative risk management. Concepts, techniques and tools
• The Johnson-Lindenstrauss transform itself preserves differential privacy
• Theory of Cryptography

Cited in

(1)

• Differentially private compression and the sensitivity of LZ77

This page was built for publication: Additive noise mechanisms for making randomized approximation algorithms differentially private

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6920763)