English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We develop a framework for efficiently transforming certain approximationalgorithms into differentially-private variants, in a black-box manner.Specifically, our results focus on algorithms A that output an approximation toa function f of the form $(1-a)f(x)-k \leq A(x) \leq (1+a)f(x)+k$, where $k \in\mathbb{R}_{\geq 0}$ denotes additive error and $a \in [0,1)$ denotesmultiplicative error can be``tuned" to small-enough values while incurring onlya polynomial blowup in the running time/space. We show that such algorithms canbe made DP without sacrificing accuracy, as long as the function f has smallglobal sensitivity. We achieve these results by applying the smooth sensitivityframework developed by Nissim, Raskhodnikova, and Smith (STOC 2007).  Our framework naturally applies to transform non-private FPRAS and FPTASalgorithms into $\epsilon$-DP approximation algorithms where the former caserequires an additional postprocessing step. We apply our framework in thecontext of sublinear-time and sublinear-space algorithms, while preserving thenature of the algorithm in meaningful ranges of the parameters. Our resultsinclude the first (to the best of our knowledge) $\epsilon$-edge DPsublinear-time algorithm for estimating the number of triangles, the number ofconnected components, and the weight of a minimum spanning tree of a graph. Inthe area of streaming algorithms, our results include $\epsilon$-DP algorithmsfor estimating Lp-norms, distinct elements, and weighted minimum spanning treefor both insertion-only and turnstile streams. Our transformation also providesa private version of the smooth histogram framework, which is commonly used forconverting streaming algorithms into sliding window variants, and achieves amultiplicative approximation to many problems, such as estimating Lp-norms,distinct elements, and the length of the longest increasing subsequence.

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