# How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity

arXiv: https://arxiv.org/abs/2210.03831 · HTML: https://mlsanity.com/paper/2210.03831/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Oct 2022.

## Built on by (most cited first, 1 of 1)

- [Differentially Private Synthetic Graphs Preserving Triangle-Motif Cuts](https://mlsanity.com/paper/2507.14835/) (2025)

## Abstract (arXiv)

We develop a framework for efficiently transforming certain approximation algorithms into differentially-private variants, in a black-box manner. Specifically, our results focus on algorithms A that output an approximation to a function f of the form (1-a)f(x)-k ≤ A(x) ≤ (1+a)f(x)+k, where k ∈ ℝ≥ 0 denotes additive error and a ∈ [0,1) denotes multiplicative error can be``tuned" to small-enough values while incurring only a polynomial blowup in the running time/space. We show that such algorithms can be made DP without sacrificing accuracy, as long as the function f has small global sensitivity. We achieve these results by applying the smooth sensitivity framework developed by Nissim, Raskhodnikova, and Smith (STOC 2007). Our framework naturally applies to transform non-private FPRAS and FPTAS algorithms into ε-DP approximation algorithms where the former case requires an additional postprocessing step. We apply our framework in the context of sublinear-time and sublinear-space algorithms, while preserving the nature of the algorithm in meaningful ranges of the parameters. Our results include the first (to the best of our knowledge) ε-edge DP sublinear-time algorithm for estimating the number of triangles, the number of connected components, and the weight of a minimum spanning tree of a graph. In the area of streaming algorithms, our results include ε-DP algorithms for estimating Lp-norms, distinct elements, and weighted minimum spanning tree for both insertion-only and turnstile streams. Our transformation also provides a private version of the smooth histogram framework, which is commonly used for converting streaming algorithms into sliding window variants, and achieves a multiplicative approximation to many problems, such as estimating Lp-norms, distinct elements, and the length of the longest increasing subsequence.